Skip to main content

347. Top K Frequent Elements

mediumAsked at DoorDash

Given an integer array and k, return the k most frequent elements. DoorDash uses this as a hash + heap warm-up — they want you to discuss both the heap-based O(n log k) and the bucket-sort O(n) approaches.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in DoorDash loops.

  • Glassdoor (2026-Q1)— DoorDash SWE onsite reports list Top K Frequent Elements as a near-default 'top-K' question.
  • Blind (2025-12)— DoorDash backend SDE reports note the bucket-sort O(n) as the actual interview signal.

Problem

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

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.

Examples

Example 1

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

Example 2

Input
nums = [1], k = 1
Output
[1]

Approaches

1. Bucket sort (optimal O(n))

Count frequencies. Bucket[i] = list of values with frequency i. Walk buckets from high to low, collect first k.

Time
O(n)
Space
O(n)
function topKFrequent(nums, k) {
  const count = new Map();
  for (const num of nums) count.set(num, (count.get(num) || 0) + 1);
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [val, freq] of count) buckets[freq].push(val);
  const result = [];
  for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
    for (const v of buckets[i]) {
      result.push(v);
      if (result.length === k) return result;
    }
  }
  return result;
}

Tradeoff: DoorDash's preferred answer. O(n) because frequencies are bounded by n — bucket[i] for i in [0, n]. Cleanest narration: 'frequencies live in [1, n], so bucketing by frequency is O(n).'

2. Heap-based O(n log k)

Build a min-heap of size k over (frequency, value) pairs. Pop smaller frequencies as we go.

Time
O(n log k)
Space
O(n + k)
function topKFrequentHeap(nums, k) {
  const count = new Map();
  for (const num of nums) count.set(num, (count.get(num) || 0) + 1);
  const heap = [];
  function push(item) {
    heap.push(item);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p][0] > heap[i][0]) { [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; }
      else break;
    }
  }
  function pop() {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length) {
      heap[0] = last;
      let i = 0;
      while (true) {
        const l = 2*i+1, r = 2*i+2;
        let small = i;
        if (l < heap.length && heap[l][0] < heap[small][0]) small = l;
        if (r < heap.length && heap[r][0] < heap[small][0]) small = r;
        if (small === i) break;
        [heap[i], heap[small]] = [heap[small], heap[i]];
        i = small;
      }
    }
    return top;
  }
  for (const [val, freq] of count) {
    push([freq, val]);
    if (heap.length > k) pop();
  }
  return heap.map((h) => h[1]);
}

Tradeoff: Standard textbook answer. O(n log k) is better when k is much smaller than n. Bucket sort beats it asymptotically but is wasteful when k is tiny.

DoorDash-specific tips

DoorDash interviewers grade specifically on whether you derive the BUCKET SORT. State 'frequencies are bounded by n, so I can bucket by frequency for O(n)' before coding. Heap is acceptable; bucket sort earns the strong-yes.

Common mistakes

  • Using sort on the frequency map — O(n log n), works but suboptimal.
  • Off-by-one on the bucket size (must be nums.length + 1 because frequency could equal n).
  • Returning the frequencies instead of the values.

Follow-up questions

An interviewer at DoorDash may pivot to one of these next:

  • Top K Frequent Words (LC 692) — same shape with string tie-breaking.
  • K Closest Points to Origin (LC 973) — heap variant.
  • Sort Characters By Frequency (LC 451) — sort the entire output.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is bucket sort O(n) here?

Because frequencies live in [1, n] — a bounded range. We allocate n+1 buckets and walk them once. Total work is O(n).

When would I prefer heap?

When the alphabet of distinct values is huge but k is tiny — the heap is O(unique * log k), which can beat bucket sort's O(n) constant factor.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Top K Frequent Elements and other DoorDash interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →