Top K Frequent Elements

Given an integer array, return the k most frequent elements. The order of the result does not matter.

Function signature

func TopKFrequent(nums []int, k int) []int

Inputs / outputs

• nums: array of integers.
• k: number of most frequent elements to return.
• Return: the k most frequent elements in any order.

Example

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

Constraints

• 1 <= k <= number of distinct elements <= len(nums)

Core idea (near-solution)

Count frequencies, then keep a min-heap of size k by frequency. The heap contains the k most frequent items.

Invariant: after processing all frequencies, the heap holds exactly the top-k elements.

Algorithm (step-by-step)

1. Build a frequency map for nums.
2. Push (num, freq) into a min-heap.
3. If heap size exceeds k, pop the smallest frequency.
4. Pop all heap elements into the result list.

Correctness sketch

• Invariant: after processing all frequencies, the heap holds exactly the top-k elements.
• The heap always maintains its ordering invariant.
• Pushing and popping preserves the set of best candidates so far.
• The final heap contents/top yields the correct answer.

Trace (hand walkthrough)

Example input:
nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Walk:
- counts: 1->3, 2->2, 3->1
- min-heap size 2 keeps (1,3),(2,2); push (3,1) then pop it
- heap elements -> [1,2]

Pitfalls to avoid

• Sorting all elements by frequency (O(n log n)) when O(n log k) is enough.
• Forgetting to pop when heap size exceeds k.

Complexity

• Time: O(n log k).
• Extra space: O(n) for the frequency map and heap.

Implementation notes (Go)

• Use container/heap with Less comparing frequencies.
• Results can be returned in any order; tests typically sort before comparison.