Topic · Hash MapMedium
Top K Frequent Elements
Understand the problem
Given an integer array nums and an integer k, return the k most frequent elements in the array. The result can be in any order.
Example:
ts
nums = [1, 1, 1, 2, 2, 3], k = 2
output = [1, 2] // 1 appears 3 times, 2 appears 2 times
nums = [1], k = 1
output = [1]The problem guarantees the answer is unique — there is no frequency tie at the k-th position.
Constraint: k ≤ the number of distinct elements in the array.
Basic approach
O(n log n) time, O(n) spacets
function topKFrequent(nums: number[], k: number): number[] {
const freq = new Map<number, number>()
for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1)
// Sort by frequency descending → take the first k
return [...freq.entries()]
.sort((a, b) => b[1] - a[1])
.slice(0, k)
.map(([val]) => val)
}Why this approach is slow:
Sorting the whole hash map takes O(n log n).
For small k that is wasteful — you only need the k top elements, not the full ordering.
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.