How do you approach Top K Frequent Elements?

Count the frequency of each element using a hash map.

What is the time complexity of Top K Frequent Elements?

Time complexity: O(n). Space complexity: O(n).

What are common mistakes on Top K Frequent Elements?

Storing the current value before checking for its complement, which lets an element pair with itself. Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n). Using a plain object as the map when keys may be numbers or __proto__; a real hash-map type keeps key identity intact.

gitGood.dev

← Back to problems

Top K Frequent Elements

MediumAlgorithms

Description

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1

Input: nums = [1,1,1,2,2,3], k = 2

Output: [1,2]

Example 2

Input: nums = [1], k = 1

Output: [1]

Constraints

- 1 <= nums.length <= 10^5 - -10^4 <= nums[i] <= 10^4 - k is in the range [1, the number of unique elements in the array]. - It is guaranteed that the answer is unique.

Top K Frequent Elements: approach, complexity and pitfalls

A medium arrays & hashing problem, graded against 6 test cases (3 of them hidden).

The pattern: Arrays & Hashing

Hash maps and sets to trade memory for time - the most common first instinct in interviews.

Reach for it when you see: "Have I seen this before?", counting occurrences, or an O(n²) scan you want to make O(n).

More Arrays & Hashing problems →

If you are stuck

Show the 3-step hint ladder

Count the frequency of each element using a hash map.
You can sort by frequency, or use bucket sort for O(n) time.
Bucket sort: create buckets indexed by frequency, then collect from highest frequency.

The optimal approach

Show the approach: Bucket Sort

Count frequencies with a hash map, then use bucket sort. Create an array of buckets where index = frequency. Collect elements from highest frequency buckets until we have k elements.

Time: O(n)
Space: O(n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.

Common Arrays & Hashing mistakes

These apply to the pattern as a whole, not just this problem.

Storing the current value before checking for its complement, which lets an element pair with itself.
Reaching for a sort to deduplicate when a set does it in one pass - that swap quietly costs you the O(n).
Using a plain object as the map when keys may be numbers or `__proto__`; a real hash-map type keeps key identity intact.