Top K Frequent Elements

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

Why this is worth learning

First count occurrences, then rank distinct values by their counts. The heap entries are values with frequencies, not individual occurrences.

Before coding: one-minute experiment

If frequencies are a:5, b:3, c:3 and k=2, must a correct answer always contain b?

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)

Sorting distinct values by their final counts is a straightforward baseline. Individual occurrences are not independent ranking candidates: the whole input must first establish each value’s count. Once counts are fixed, retain the k strongest count entries and expose the weakest retained frequency for eviction. Numeric value does not determine priority, and equal cutoff frequencies may leave more than one correct selected set.

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

Once the frequency map is complete, process each distinct value once. Maintain a min-heap of the k strongest frequency entries processed so far; inserting a new entry and removing the weakest when oversized preserves this property. At completion no excluded value has frequency greater than a retained minimum, so the result is a valid top-k selection. Equal frequencies at the cutoff can admit multiple correct subsets, and map iteration can vary their choice. Every returned value must be distinct; sorting output alone does not make a test robust to a cutoff tie.

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.

Debugging lens

Check length k, no duplicates, membership in the input, and that no excluded frequency exceeds any selected one. Do not assert deterministic ordering from Go map traversal.

Complexity

For n entries and U distinct values, expected time O(n + U log(k+1)); auxiliary space O(U+k), which is O(U) since k<=U.

Implementation notes (Go)

• Use container/heap with Less comparing frequencies.
• Results may be in any order. At a cutoff tie, more than one selected set is valid; sorting alone is not enough for validation. Check k distinct input values and that no excluded value has greater frequency than a selected one.

Reconstruction checkpoint

If frequencies are a:5, b:3, c:3 and k=2, must a correct answer always contain b?

Return to Heap / Priority Queue · Module quiz