SyntaxPilot
Courses/DSA and Coding Problems/Lesson 43
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 43 of 90

Heaps: top K frequent elements

queued

These are the notes for DSA episode 43. We meet a new data structure, the heap, the engine behind leaderboards, trending lists and task schedulers, and use it on a very common interview problem: return the k most frequent values of an array. We start from a real-life problem (today's top 5 songs out of 2 lakh plays), solve it the obvious way (recount everything for every pick, O(k · n²)), watch it hit Time Limit Exceeded, count once with a HashMap, learn the heap from zero (with Java's PriorityQueue), and finish with a min-heap of size k: O(n + m log k). Every program below was run with javac 21 with an 8-second limit (like the SyntaxPilot compiler), and every output shown is real.

The problem, in real life

A music app logs the song id of every play: 4021, 17, 4021, … By evening there are 2 lakh plays of about 44,000 different songs. The home screen shows today's top 5, the five songs played most often, and refreshes every few seconds for millions of users. So finding those five must be fast.

In the music app In code
The log of plays the array nums
A song's number of plays its frequency (count)
The number of different songs m, the number of distinct values
The top 5 songs the k most frequent values, k = 5

Every word, from zero

  • Frequency: how many times a value appears in the array.
  • Distinct values: the different values, each counted once; we call their number m (m ≤ n).
  • HashMap: key → value map with O(1) average get / put; here song id → count.
  • cnt.merge(x, 1, Integer::sum): if x is not in the map, store 1; otherwise store old count + 1.
  • Complete binary tree: every level is full except maybe the last, which is filled from the left.
  • Min-heap: a complete binary tree where every parent ≤ its children, so the smallest item is at the top (root). A max-heap has every parent ≥ its children.
  • Array storage: a complete tree has no gaps, so it is stored in a plain array; the children of index i are at 2i + 1 and 2i + 2, its parent at (i - 1) / 2.
  • peek / offer / poll: look at the top (O(1)), add an item (O(log n)), remove the top (O(log n)).
  • Sift up / sift down: after offer, the new item swaps upward while it is smaller than its parent; after poll, the last item is moved to the top and swaps downward with its smaller child.
  • PriorityQueue: Java's heap (java.util); a min-heap by default.
  • Comparator: a rule for comparing two items a and b: negative means a comes first, positive means b comes first, 0 means equal. Written as a lambda: (a, b) -> cnt.get(a) - cnt.get(b).

Problem statement

Given an integer array nums and an integer k, return the k most frequent elements, in any order. The answer is guaranteed to be unique.

nums k answer
[1, 1, 1, 2, 2, 3] 2 [1, 2]
[1] 1 [1]

Constraints: up to 1 lakh numbers; follow-up: do better than O(n log n).

Brute force: recount everything, k times

import java.util.*;

public class Main {
    static int[] bruteTopK(int[] nums, int k) {
        List<Integer> taken = new ArrayList<>();
        for (int t = 0; t < k; t++) {
            int best = 0, bestCount = -1;
            for (int x : nums) {
                if (taken.contains(x)) continue;
                int c = 0;
                for (int y : nums) if (y == x) c++;
                if (c > bestCount) { bestCount = c; best = x; }
            }
            taken.add(best);
        }
        int[] ans = new int[k];
        for (int t = 0; t < k; t++) ans[t] = taken.get(t);
        return ans;
    }
    public static void main(String[] args) {
        int[] a = {1, 1, 1, 2, 2, 3};
        System.out.println(Arrays.toString(bruteTopK(a, 2)));
        System.out.println(Arrays.toString(bruteTopK(new int[]{1}, 1)));
    }
}

Real output:

[1, 2]
[1]

2 lakh plays: Time Limit Exceeded

    static int[] bigInput() {
        Random rnd = new Random(43);
        int[] a = new int[200000];
        for (int j = 0; j < a.length; j++) {
            double r = rnd.nextDouble();
            a[j] = (int) (50000 * r * r * r);
        }
        return a;
    }
    // in main:
        int[] plays = bigInput();
        long t0 = System.nanoTime();
        int[] top = bruteTopK(plays, 5);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println(Arrays.toString(top) + ", " + ms + " ms");

Cubing the random number makes small ids much more common, like real hit songs (song 0 has 5,394 plays, song 4 has 643; there are 44,009 different songs). In the SyntaxPilot compiler: Time Limit Exceeded (stopped after 8 s); it did not finish in 100 s without a limit either.

Why it is slow

  • For each of the n numbers we scan all n numbers to count it: 2 lakh × 2 lakh = 4 × 10^10 steps per round.
  • Times k rounds: O(k · n²).
  • A hit song played 5,000 times is counted all over again 5,000 times, in every round.

Fix 1: count once with a HashMap

        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) cnt.merge(x, 1, Integer::sum);

One pass: O(n). Now we have m counts. Sorting all of them by count would be O(m log m), but we only need k of them.

Heaps, from zero

Real-life picture: a merit board with K seats. Only the top K students sit there, and the weakest of them always sits by the door. When a better student arrives, they take a seat; now there are K + 1, so the one by the door leaves. That is a min-heap of size K.

A min-heap stored in an array: [2, 5, 3, 9, 7]

          2            index 0
        /   \
       5     3         indexes 1, 2   (children of i: 2i+1, 2i+2)
      / \
     9   7             indexes 3, 4
  • peek() returns 2, the top: O(1).
  • offer(1): 1 goes into the next free spot (index 5, child of 3); 1 < 3 → swap; 1 < 2 → swap; 1 is the new top. At most one swap per level: O(log n).
  • poll(): remove the top, move the last item to the top, swap it down with its smaller child until the rule holds: O(log n).
  • A heap is not sorted: only the top is guaranteed to be the smallest.
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(9); pq.offer(2); pq.offer(7); pq.offer(5);
        System.out.println("peek: " + pq.peek());
        System.out.println("poll: " + pq.poll());
        System.out.println("poll: " + pq.poll());
        System.out.println("size: " + pq.size());

Real output:

peek: 2
poll: 2
poll: 5
size: 2

The key insight: a min-heap of size k, keyed by count

  1. Count with the HashMap: O(n).
  2. Make a min-heap of values ordered by their counts: new PriorityQueue<>((a, b) -> cnt.get(a) - cnt.get(b)). The least frequent value is on top.
  3. Offer every distinct value; whenever the heap holds more than k, poll (the least frequent leaves).
  4. The heap now holds the k most frequent values.

On example 1 (counts 1→3, 2→2, 3→1, k = 2):

offer heap (top first) size > k?
1 (×3) 1 no
2 (×2) 2, 1 no
3 (×1) 3, 2, 1 yes → poll 3
2, 1 answer: [1, 2]

The heap never holds more than k + 1 items, so each offer / poll is O(log k).

The optimal solution in Java

import java.util.*;

public class Main {
    static int[] topK(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) cnt.merge(x, 1, Integer::sum);
        PriorityQueue<Integer> heap =
            new PriorityQueue<>((a, b) -> cnt.get(a) - cnt.get(b));
        for (int x : cnt.keySet()) {
            heap.offer(x);
            if (heap.size() > k) heap.poll();
        }
        int[] ans = new int[k];
        for (int t = k - 1; t >= 0; t--) ans[t] = heap.poll();
        return ans;
    }
    public static void main(String[] args) {
        int[] a = {1, 1, 1, 2, 2, 3};
        System.out.println(Arrays.toString(topK(a, 2)));
        System.out.println(Arrays.toString(topK(new int[]{1}, 1)));
        System.out.println(Arrays.toString(topK(new int[]{-1, -1, 5, 7, 7, 7}, 2)));
        System.out.println(Arrays.toString(topK(new int[]{4, 4, 9}, 2)));
    }
}

Real output:

[1, 2]
[1]
[7, -1]
[4, 9]

Polling into the answer from the back puts the most frequent value first. When k equals the number of distinct values ([4, 4, 9], k = 2), every value is returned.

2 lakh plays in milliseconds

With topK(plays, 5): real output [0, 1, 2, 3, 4], 136 ms.

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

vector<int> topK(const vector<int>& nums, int k) {
    unordered_map<int, int> cnt;
    for (int x : nums) cnt[x]++;
    auto cmp = [&](int a, int b) { return cnt[a] > cnt[b]; };   // min-heap by count
    priority_queue<int, vector<int>, decltype(cmp)> heap(cmp);
    for (auto& [x, c] : cnt) {
        heap.push(x);
        if ((int)heap.size() > k) heap.pop();
    }
    vector<int> ans(k);
    for (int t = k - 1; t >= 0; t--) { ans[t] = heap.top(); heap.pop(); }
    return ans;
}

void show(const vector<int>& v) {
    cout << "[";
    for (size_t i = 0; i < v.size(); i++) cout << (i ? ", " : "") << v[i];
    cout << "]\n";
}

int main() {
    show(topK({1, 1, 1, 2, 2, 3}, 2));
    show(topK({1}, 1));
    show(topK({-1, -1, 5, 7, 7, 7}, 2));
    show(topK({4, 4, 9}, 2));
}

C++'s priority_queue is a max-heap by default; the comparator cnt[a] > cnt[b] turns it into a min-heap by count. Real output (g++ -O2 -std=c++17): the same four lines as Java.

The same solution in Python

import heapq
from collections import Counter

def top_k(nums, k):
    cnt = Counter(nums)
    heap = []                                # min-heap of (count, value)
    for x, c in cnt.items():
        heapq.heappush(heap, (c, x))
        if len(heap) > k:
            heapq.heappop(heap)              # drop the least frequent
    ans = [0] * k
    for t in range(k - 1, -1, -1):
        ans[t] = heapq.heappop(heap)[1]
    return ans

print(top_k([1, 1, 1, 2, 2, 3], 2))
print(top_k([1], 1))
print(top_k([-1, -1, 5, 7, 7, 7], 2))
print(top_k([4, 4, 9], 2))

heapq is a min-heap on a plain list; tuples compare by their first item (the count). Real output: the same four lines. (Counter(nums).most_common(k) is a one-line alternative.)

Two real bugs

Bug 1: ordering the heap by value, not by count

            new PriorityQueue<>((a, b) -> a - b);

Real output on example 1: [3, 2]. The heap threw out the smallest value (1, the most frequent) and kept the biggest values.

Bug 2: never trimming the heap to k

        for (int x : cnt.keySet()) {
            heap.offer(x);                     // no "if (heap.size() > k) heap.poll();"
        }

Real output on example 1: [2, 3]. The heap kept all three values; the final polls took out the two weakest (3, then 2).

Complexity

Approach Time Space 2 lakh plays
Recount for every pick O(k · n²) O(k) minutes → TLE
HashMap + sort all counts O(n + m log m) O(m) fast, but sorts everything
HashMap + min-heap of size k O(n + m log k) O(m + k) 0.14 s
HashMap + bucket sort O(n) O(n) fastest in theory (practice 2)

n = length of nums, m = number of distinct values.

Common mistakes

Mistake What you see Why Fix
(a, b) -> a - b [3, 2] instead of [1, 2] ordered by value, not by count cnt.get(a) - cnt.get(b)
No poll when size > k [2, 3] instead of [1, 2] the weak ones never leave if (heap.size() > k) heap.poll();
Counting by scanning, k rounds Time Limit Exceeded O(k · n²) one HashMap pass
A max-heap of every value works, but O(m log m) everything is kept min-heap of size k
Expecting a heap to be sorted printing the heap shows a strange order only the top is guaranteed poll repeatedly to get sorted order
a - b comparators with huge numbers wrong order int overflow in the subtraction Integer.compare(a, b)

Read play logs line by line (songId,userId), keep a HashMap of counts, and every 1,000 plays print the current top 5 with their counts, like a live trending board. Then add a twist: count each user at most once per song (a HashSet of songId:userId pairs).

Practice

  1. Kth largest element (LeetCode 215).
Solution

Keep a min-heap of the k largest values seen so far; its top is the kth largest.

    static int kthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int x : nums) {
            heap.offer(x);
            if (heap.size() > k) heap.poll();
        }
        return heap.peek();
    }

kthLargest({3, 2, 1, 5, 6, 4}, 2) → 5. Real output. O(n log k).

  1. Top K frequent in O(n) with bucket sort.
Solution

A count is between 1 and n, so make n + 1 buckets: bucket c holds the values seen exactly c times. Walk the buckets from n down to 1.

    static int[] topKBucket(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) cnt.merge(x, 1, Integer::sum);
        List<List<Integer>> bucket = new ArrayList<>();
        for (int c = 0; c <= nums.length; c++) bucket.add(new ArrayList<>());
        for (var e : cnt.entrySet()) bucket.get(e.getValue()).add(e.getKey());
        int[] ans = new int[k];
        int t = 0;
        for (int c = nums.length; c >= 1 && t < k; c--)
            for (int x : bucket.get(c)) if (t < k) ans[t++] = x;
        return ans;
    }

topKBucket({1, 1, 1, 2, 2, 3}, 2) → [1, 2]. Real output.

  1. K closest points to the origin (LeetCode 973).
Solution

Now we want the k smallest distances, so keep a max-heap of size k by squared distance: the farthest of the k is on top and leaves first.

    static int[][] kClosest(int[][] pts, int k) {
        PriorityQueue<int[]> heap = new PriorityQueue<>(
            (a, b) -> (b[0] * b[0] + b[1] * b[1]) - (a[0] * a[0] + a[1] * a[1]));
        for (int[] p : pts) {
            heap.offer(p);
            if (heap.size() > k) heap.poll();
        }
        return heap.toArray(new int[0][]);
    }

kClosest({{3, 3}, {5, -1}, {-2, 4}}, 2) → [[-2, 4], [3, 3]]. Real output (any order is accepted).

Quick quiz

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(8); pq.offer(3);
pq.offer(6); pq.offer(1);
pq.poll();
System.out.println(pq.peek());

What is printed: 8, 3, 6 or 1?

Answer

3. A PriorityQueue is a min-heap: poll() removes the smallest (1), and the new top is the next smallest, 3.

Interview questions

  1. Why a min-heap for the top k largest? The heap holds the current best k; the weakest of them must be the one that leaves, so it has to be on top.
  2. Why is the heap O(log k) per operation and not O(log n)? It never holds more than k + 1 items.
  3. Heap vs sorting? Sorting all m counts is O(m log m); a size-k heap is O(m log k), much better when k is small, and it works on a stream.
  4. Can you do O(n)? Yes: bucket sort by count (practice 2), or Quickselect on the distinct values (average O(m)).
  5. How is a heap stored? In an array: the children of i are 2i + 1 and 2i + 2, the parent is (i - 1) / 2.
  6. What does PriorityQueue.toString() show? The internal array order, which is not sorted.

Glossary

Term Meaning
Frequency How many times a value appears
Distinct values The different values, each counted once (m of them)
HashMap Key → value map with O(1) average get / put
merge(x, 1, Integer::sum) Put 1 for a new key, or add 1 to the old value
Complete binary tree Every level full except the last, filled from the left
Min-heap / max-heap Every parent ≤ / ≥ its children; the smallest / largest is on top
peek Look at the top of the heap: O(1)
offer Add to the heap, then sift up: O(log n)
poll Remove the top, move the last item up, sift down: O(log n)
Sift up / sift down Swapping an item up or down until the heap rule holds
PriorityQueue Java's heap; a min-heap by default
Comparator A rule comparing two items: negative → first item comes first
Lambda A short function written inline: (a, b) -> ...
Bucket sort Grouping items into buckets by a small key (here the count)
O(k · n²), O(n + m log k) The running times of the brute force and the heap solution
Time Limit Exceeded (TLE) The program was stopped for running too long (8 s in the SyntaxPilot compiler)

Summary

  • Recounting for every pick is O(k · n²): TLE on 2 lakh numbers.
  • Count once with a HashMap: O(n).
  • A min-heap is a complete binary tree in an array with every parent ≤ its children; the smallest is on top. PriorityQueue: peek O(1), offer / poll O(log n).
  • Keep a min-heap of size k ordered by count; poll whenever it grows past k. O(n + m log k) time, O(m + k) space.

Next episode: Median from a data stream with two heaps (hard).