Top K Problems

“Top K” problems ask for the K largest, K smallest, or K most frequent elements. A heap (priority queue) keeps the candidate set small and yields O(n log K) time. See [Heap Fundamentals](/blog/algorithms/heap-top-k/heap-fundamentals) for the basics and [Streaming Scenarios](/blog/algorithms/heap-top-k/streaming-scenarios) when data arrives in a stream.

K Largest Elements

Keep a min-heap of size K. Scan the array: if the heap has fewer than K elements, add the value; otherwise, if the current value is greater than the heap’s minimum, replace the minimum with it. The heap then contains the K largest elements; the root is the K-th largest.

Java
public int[] topKLargest(int[] nums, int k) {
    Queue<Integer> minHeap = new PriorityQueue<>();
    for (int x : nums) {
        minHeap.offer(x);
        if (minHeap.size() > k) minHeap.poll();
    }
    return minHeap.stream().mapToInt(i -> i).toArray();
}

Time O(n log K), space O(K).

K Smallest Elements

Use a max-heap of size K: keep the K smallest by evicting the maximum when the heap exceeds K. Or use a min-heap and poll K times (O(n + K log n)).

K Most Frequent Elements

  1. Count frequency of each element (e.g. with a hash map).
  2. Use a min-heap of size K over (frequency, value). Iterate entries: add to heap; if size > K, poll the smallest frequency. The heap then holds the K most frequent.
Java
public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int x : nums) freq.merge(x, 1, Integer::sum);
    Queue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
        heap.offer(new int[]{e.getKey(), e.getValue()});
        if (heap.size() > k) heap.poll();
    }
    return heap.stream().mapToInt(a -> a[0]).toArray();
}

Summary

  • K largest: min-heap of size K, evict minimum when full.
  • K smallest: max-heap of size K or min-heap + K polls.
  • K most frequent: count frequencies, then min-heap by frequency of size K. All O(n log K) with O(K) space.