Free lesson · DSA Mastery - Interview Prep, End to End

Top K Frequent Elements

Medium8 min readdsaheaps

Top K Frequent Elements

Top K Frequent Elements is the frequency variant of the Top K pattern: return the k most frequently occurring elements in an array. It is a two-phase solution - first tally each element's count in a hash map (O(n)), then select the K highest counts using a size-K min-heap keyed on frequency (evict the least frequent keeper). It also admits a bucket-sort-by-frequency alternative that runs in O(n) when counts are bounded, contrasting the general heap approach with a counting-based optimization for the same top-K-by-count goal. We present the count + size-K min-heap (canonical) and the bucket-sort approach.

The insight: "most frequent" first requires knowing each element's frequency, so phase one is a counting pass into a map. Then it becomes a Top K problem keyed on frequency rather than value - keep the K most frequent in a size-K min-heap ordered by count, so the least frequent keeper sits at the top for eviction. Because frequencies range only from 1 to n, a second route exists: bucket the elements by exact frequency and read the highest non-empty buckets, achieving O(n).

The Problem

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]

Explanation: 1 appears 3 times, 2 appears 2 times, 3 appears once. Top 2 by frequency: [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.

Follow-up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

Approaches Overview

#	Approach	Time	Space	Verdict
1	Count + sort by frequency	O(n log n)	O(n)	Baseline
2	Count + size-K min-heap by frequency	O(n log k)	O(n)	Canonical
3	Count + bucket sort by frequency	O(n)	O(n)	Meets follow-up

All three first tally counts in O(n). The baseline then sorts unique elements by frequency - O(n log n), failing the follow-up. The heap keeps the K most frequent in a size-K min-heap keyed on count - O(n log k). The bucket-sort approach places elements into buckets indexed by exact frequency (1..n) and reads from the highest bucket down - O(n), meeting the follow-up. The heap is the canonical Top K realization; bucket sort is the counting optimization.

Approach 1: Count + Sort - Baseline

The Idea

Build a frequency map, then sort the unique keys by descending frequency and take the first K. Simple but the sort is O(u log u) on u unique elements, up to O(n log n) - failing the follow-up's requirement.

Complexity

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

Approach 2: Count + Size-K Min-Heap by Frequency - Canonical

The Idea

Build a frequency map in O(n). Maintain a min-heap of (element, frequency) ordered by frequency, capped at size K: for each unique element, offer it; if the heap exceeds K, poll the least frequent. After processing all unique elements, the heap holds the K most frequent; drain it into the result. Keyed on frequency, the size-K min-heap keeps the most frequent by evicting the least frequent keeper.

Logic Flowchart

graph TD
    A["count frequencies into map (O(n))"] --> B["min-heap by frequency, capacity k"]
    B --> C["for each (element, freq) in map"]
    C --> D["offer (element, freq)"]
    D --> E{"heap size > k?"}
    E -->|Yes| F["poll least-frequent keeper"]
    E -->|No| G["keep"]
    F --> C
    G --> C
    C --> H["drain heap → k most frequent elements"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the count-then-heap approach. Frequencies are tallied, then each unique element enters a size-k min-heap keyed on frequency, evicting the least frequent keeper, and the heap is drained to give the k most frequent.

Code

public static int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int n : nums) count.merge(n, 1, Integer::sum);     // phase 1: tally O(n)

    // min-heap by frequency; keeps the k most frequent
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);  // [element, freq]
    for (Map.Entry<Integer, Integer> e : count.entrySet()) {
        heap.offer(new int[]{e.getKey(), e.getValue()});
        if (heap.size() > k) heap.poll();                   // evict least frequent
    }

    int[] result = new int[k];
    for (int i = 0; i < k; i++) result[i] = heap.poll()[0]; // drain (any order)
    return result;
}

// Usage:
// topKFrequent([1,1,1,2,2,3], 2) -> [1,2] (order not required)

This Java code tallies frequencies, then runs a size-k min-heap keyed on frequency over the unique elements, evicting the least frequent keeper, and drains the heap to return the k most frequent elements.

Step-by-Step Walkthrough

A frame-by-frame trace on nums = [1,1,1,2,2,3], k = 2:

graph LR
    F0["count: {1:3, 2:2, 3:1}"]
    F1["offer (1,3); offer (2,2); heap[(2,2),(1,3)] size 2 = k"]
    F2["offer (3,1) → heap size 3 > 2 → poll least freq (3,1)"]
    F3["heap holds (2,2),(1,3) → top-2 frequent = [2,1] (any order)"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F2 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough finds the top two frequent. After counting, the size-two min-heap keeps elements one and two and evicts three, the least frequent, leaving one and two as the answer.

Result: [1,2] (any order).

Complexity

Time: O(n log k) - O(n) count plus O(u log k) heap over u unique elements. Space: O(n).

Approach 3: Count + Bucket Sort by Frequency - Meets Follow-Up

The Idea

After counting, create buckets indexed by frequency (0..n), placing each element into the bucket equal to its count. Then scan buckets from highest frequency down, collecting elements until you have K. Since frequencies are bounded by n, this is O(n) - no comparison sort, no heap.

Complexity

Time: O(n). Space: O(n) for the buckets.

Complexity Comparison

Approach	Time	Space	Key Idea	When to Use
Count + sort	O(n log n)	O(n)	Sort uniques by frequency	Simplest, fails follow-up
Count + size-K min-heap	O(n log k)	O(n)	Keep k most frequent, evict least	Canonical Top K
Count + bucket sort	O(n)	O(n)	Index by exact frequency	Meets O(n) follow-up

All three share the O(n) counting phase; they differ in the selection phase. The heap is the general Top K realization (O(n log k), great when K is small). Bucket sort exploits that frequencies are bounded integers to drop the log factor entirely, achieving the O(n) the follow-up asks for. Knowing both - heap for generality, bucket sort for bounded keys - is the lesson.

Variations & Follow-ups

Why is this a two-phase problem, and why count first?

"Most frequent" is a statement about counts, which aren't given - they must be derived. So phase one is an unavoidable counting pass that builds a value → frequency map in O(n). Only once frequencies exist does the problem reduce to a familiar form: select the K elements with the highest counts, i.e., Top K keyed on frequency. Separating the phases clarifies the cost (O(n) to count, then a selection step) and lets you pick the selection method independently - sort, heap, or buckets. Conflating them or trying to rank before fully counting leads to bugs, since an element's frequency isn't known until the whole array is scanned.

Why a size-K min-heap keyed on frequency, not a max-heap?

This is the same Top K inversion as before, applied to frequency as the key. To keep the K most frequent, you repeatedly evict the least frequent of your current keepers - so you want that least-frequent keeper exposed at the top, which a min-heap (ordered by frequency) provides. Each unique element is offered; if the heap exceeds K, the top (lowest frequency among keepers) is polled and discarded, since K others are at least as frequent and it can't be in the top K. A max-heap would surface the most frequent keeper - exactly the one you want to keep - and evicting it would be wrong. Min-heap-for-K-largest, here with "largest" meaning "most frequent."

Why does bucket sort achieve O(n), and when is it the better choice?

An element's frequency is an integer between 1 and n (it can't appear more than n times), so frequencies live in a small, bounded range. That makes them suitable for counting/bucket sort: create an array of buckets indexed by frequency, drop each element into its frequency's bucket in O(1), then walk buckets from index n down to 1, collecting elements until K are gathered. No comparisons, no log factor - O(n) total. It beats the heap when K is large (heap approaches O(n log n)) or when the bounded-frequency structure is available. The heap remains preferable when you can't afford O(n) buckets or when frequencies aren't conveniently bounded; bucket sort is the specialized optimization the follow-up rewards.

Why does the heap iterate over unique elements rather than all n?

The selection phase ranks distinct elements by their frequency, so it operates on the u unique keys of the count map, not the original n array positions. If many duplicates exist, u << n, so the heap phase is O(u log k) - often much less than O(n log k). Iterating the array again instead of the map would redundantly re-offer the same element many times, inflating cost and risking duplicate results. Working from the map ensures each element is considered once with its final frequency. This is why the count map is essential beyond just computing frequencies: it also deduplicates the candidate set for the selection phase.

What about edge cases?

k equals the number of unique elements: All uniques are returned; the heap never evicts (or evicts nothing meaningful).
Single element (Example 2): One unique value, returned directly.
All elements distinct: Every frequency is 1; ties broken arbitrarily (problem guarantees a unique answer set).
k = 1: Return the single most frequent element.

Common Interview Pitfalls

Using a max-heap of all uniques. For top-K-by-frequency, a size-K min-heap is the efficient choice; a full max-heap is O(u log u).
Sorting and failing the follow-up. The O(n log n) sort doesn't meet the required sub-n log n bound; use heap or buckets.
Iterating the array instead of the count map. Re-offers duplicates; rank uniques from the map.
Bucket index off-by-one. Frequencies run 1..n; size the bucket array accordingly and scan from the top.

Why This Topic Matters

Top K Frequent Elements is the frequency variant of Top K: tally counts in O(n), then select the K highest with a size-K min-heap keyed on frequency. It reinforces the min-heap-for-most inversion on a derived key and introduces the bucket-sort-by-frequency optimization that meets an O(n) requirement - the count-then-select two-phase shape recurs across frequency-ranking problems.

The next topic, K Closest Points to Origin, closes the section with the K-smallest-by-computed-key form: given points in the plane, return the k closest to the origin by Euclidean distance. A size-K max-heap keyed on squared distance keeps the K closest - the farthest keeper sits at the top for eviction when a nearer point arrives. It also admits a quickselect on distance for O(n) average time, mirroring the heap-versus-quickselect trade-off framed in the sub-group introduction, and rounds out the Top K pattern with a geometric, computed-key example before the course moves on to the Intervals section.

Back to DSA Mastery - Interview Prep, End to End