347. Top K Frequent Elements

Q: Why is O(n log k) better than O(n log n)?

When k is small (e.g., top 50 out of 10,000 instruments), log k ≈ 6 while log n ≈ 13. The heap approach is roughly twice as fast in this scenario.

Q: Why does the bucket sort work in O(n)?

Frequencies are integers in [1, n]. An array of n+1 buckets is a form of counting sort — O(n) to fill, O(n) to drain. No comparison-based sorting.

Q: How would you handle a live-updating top-k?

Maintain a min-heap of size k. On each update, if the element's frequency exceeds the heap minimum, pop the minimum and push the new element. Each update is O(log k).

mediumAsked at DRW

DRW asks Top K Frequent Elements to probe heap vs. bucket-sort trade-offs — decisions that matter when ranking the k most-traded instruments by volume or the k most-active order IDs in a session. O(n log k) with a heap is expected; O(n) with bucket sort earns extra credit.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in DRW loops.

Glassdoor (2026-Q1)— DRW SWE candidates report top-k and heap-based ranking problems as recurring medium-difficulty questions in coding rounds.
Blind (2025-11)— DRW interview threads note that interviewers specifically ask for the O(n) bucket-sort solution after accepting the heap approach.

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]

Explanation: 1 appears 3 times, 2 appears 2 times — top 2.

Example 2

Input

nums = [1], k = 1

Output

[1]

Explanation: Single element, k=1.

Approaches

1. Min-heap of size k

Count frequencies with a hash map. Use a min-heap of size k — push each element; if the heap exceeds size k, pop the minimum-frequency element. The heap retains the k most frequent.

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

function topKFrequent(nums, k) {
  // Count frequencies
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);

  // Min-heap simulation: sort all unique elements by frequency, take top k
  // (JS has no built-in heap; for interview, sort the entries)
  const entries = [...freq.entries()]; // [value, count]
  entries.sort((a, b) => b[1] - a[1]);
  return entries.slice(0, k).map(e => e[0]);
}

Tradeoff: O(n log n) as written (sorting all unique elements). For a true O(n log k) solution, implement a min-heap of capacity k. Flag this to the interviewer — explain the heap approach even if the JS sort is what you code.

2. Bucket sort (O(n))

Frequencies range from 1 to n. Create n+1 buckets indexed by frequency. Collect elements from the highest-frequency bucket down until k elements are gathered.

Time: O(n)
Space: O(n)

function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);

  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [val, count] of freq) buckets[count].push(val);

  const result = [];
  for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
    result.push(...buckets[i]);
  }
  return result.slice(0, k);
}

Tradeoff: O(n) time — optimal. Frequency values are bounded by n, so an array of n+1 buckets is sufficient. This is the answer DRW is looking for after you present the heap.

DRW-specific tips

Present both approaches with explicit complexity trade-offs. DRW interviewers expect: 'The heap gives O(n log k) — better than O(n log n) sort when k << n. But if k is close to n, bucket sort is O(n) with no log factor.' They will then ask: 'In a market-data session with 10 million tick events per second and n unique instruments, what is the time budget for computing the top-50 by volume every second?' — the heap approach is bounded by O(n log 50) ≈ O(6n), which is linear and fast enough.

Common mistakes

Using full sort instead of a heap — O(n log n) versus the O(n log k) the problem implies.
Bucket array of size n instead of n+1 — frequency n (all elements the same) needs index n.
Forgetting that multiple elements can share the same frequency bucket — the bucket holds an array, not a single element.
Off-by-one when collecting from high-frequency buckets — stop when result.length === k.

Follow-up questions

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

Kth Largest Element in an Array (LC 215) — use QuickSelect for O(n) average.
Top K Frequent Words (LC 692) — same pattern but with lexicographic tie-breaking.
How would you maintain the top-k instruments by traded volume in a live stream with O(log k) updates?

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 O(n log k) better than O(n log n)?

When k is small (e.g., top 50 out of 10,000 instruments), log k ≈ 6 while log n ≈ 13. The heap approach is roughly twice as fast in this scenario.

Why does the bucket sort work in O(n)?

Frequencies are integers in [1, n]. An array of n+1 buckets is a form of counting sort — O(n) to fill, O(n) to drain. No comparison-based sorting.

How would you handle a live-updating top-k?

Maintain a min-heap of size k. On each update, if the element's frequency exceeds the heap minimum, pop the minimum and push the new element. Each update is O(log k).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →