Top K Frequent Elements

Problem Statement

Given an integer array nums and an integer k, return the k most frequent elements. Results may be returned in any order.

Input

An integer array nums and the count k.

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

Output

An array of the k most-frequent values.

[1, 2]
 
// frequencies: {1: 3, 2: 2, 3: 1}
// top 2: 1 (freq 3), 2 (freq 2)

Constraints

• 1 ≤ nums.length ≤ 10⁵
• k is always valid — at least k distinct values exist.

Intuition

Two stages: (1) count frequencies with a hash-map in O(n), (2) take the top K of those by frequency. The second stage is a textbook Top-K — min-heap of size K on (frequency, value) tuples. When size exceeds K, evict the root — the element with the lowest frequency among the top-K-so-far.

freq:  {1:3, 2:2, 3:1}
 
push (3,1) → heap = [(3,1)]
push (2,2) → heap = [(2,2),(3,1)]    size == k, no evict
push (1,3) → size exceeds k → pop smallest → (1,3) evicted
                 heap = [(2,2),(3,1)]
 
result values = [2, 1]   // any order ok

Solution

import heapq
from collections import Counter
 
def topKFrequent(nums: list[int], k: int) -> list[int]:
    freq = Counter(nums)                               # O(n)
    min_heap: list[tuple[int, int]] = []               # (frequency, value)
    for val, cnt in freq.items():
        heapq.heappush(min_heap, (cnt, val))
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    return [val for _, val in min_heap]

function topKFrequent(nums: number[], k: number): number[] {
  const freq = new Map<number, number>();
  for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);
 
  // min-heap on frequency → smallest freq bubbles up, ready to evict
  const h = new Heap<[number, number]>((a, b) => a[0] - b[0]);
  for (const [val, cnt] of freq) {
    h.push([cnt, val]);
    if (h.size > k) h.pop();
  }
  const out: number[] = [];
  while (h.size > 0) out.push(h.pop()![1]);
  return out;
}

Complexity

Edge Case Thinking