Skip to main content

347. Top K Frequent Elements

mediumAsked at Robinhood

Given an integer array and integer k, return the k most frequent elements. Robinhood likes this for top-K pattern practice and as a natural lead-in to a discussion about how you'd track top-K ticker symbols by trade volume in real time.

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

Source citations

Public interview reports confirming this problem appears in Robinhood loops.

  • Glassdoor (2026-Q1)— Robinhood SWE onsite reports list Top K Frequent as a recurring round.
  • Blind (2025-10)— Robinhood SWE-II loop reports cite top-K pattern problems as a thematic favorite.

Problem

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

Constraints

  • 1 <= nums.length <= 10^5
  • 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. Frequency map + sort

Count frequencies in a hash map. Sort entries by frequency desc. Return first k keys.

Time
O(n log n)
Space
O(n)
function topKFrequentSort(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
  return [...freq.entries()].sort((a, b) => b[1] - a[1]).slice(0, k).map(e => e[0]);
}

Tradeoff: Simple but doesn't beat the n log n bound the problem asks for. Mention it, then move on.

2. Min-heap of size k

Push each (freq, num) into a min-heap. When size exceeds k, pop the min. Heap contents are the answer.

Time
O(n log k)
Space
O(n + k)
class MinHeap {
  constructor() { this.data = []; }
  push(v) { this.data.push(v); this._up(this.data.length - 1); }
  pop() { const top = this.data[0]; const last = this.data.pop(); if (this.data.length) { this.data[0] = last; this._down(0); } return top; }
  size() { return this.data.length; }
  _up(i) { while (i > 0) { const p = (i - 1) >> 1; if (this.data[p][0] <= this.data[i][0]) break; [this.data[p], this.data[i]] = [this.data[i], this.data[p]]; i = p; } }
  _down(i) { const n = this.data.length; while (true) { const l = 2*i+1, r = 2*i+2; let best = i; if (l < n && this.data[l][0] < this.data[best][0]) best = l; if (r < n && this.data[r][0] < this.data[best][0]) best = r; if (best === i) break; [this.data[best], this.data[i]] = [this.data[i], this.data[best]]; i = best; } }
}

function topKFrequentHeap(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
  const heap = new MinHeap();
  for (const [num, count] of freq) {
    heap.push([count, num]);
    if (heap.size() > k) heap.pop();
  }
  return heap.data.map(x => x[1]);
}

Tradeoff: O(n log k) beats the O(n log n) bar the problem demands. Standard top-K pattern.

3. Bucket sort by frequency (optimal)

Frequency ranges from 1 to n, so use n+1 buckets where bucket[f] holds all numbers seen f times. Scan buckets from high to low, collect k.

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 [num, count] of freq) buckets[count].push(num);
  const result = [];
  for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
    for (const num of buckets[i]) {
      result.push(num);
      if (result.length === k) return result;
    }
  }
  return result;
}

Tradeoff: True O(n) by exploiting that frequency is bounded by n. Many candidates miss this — name it explicitly to lock in the rubric points.

Robinhood-specific tips

Robinhood interviewers will accept the min-heap, but the bucket-sort optimal is the question's intended answer (the problem says 'better than O(n log n)'). Articulate why bucket sort is O(n): 'frequencies are bounded by n, so we have n+1 buckets and we read them in O(n).' If you reach for heap first, follow up with 'and there's an O(n) version using bucket sort.'

Common mistakes

  • Using a max-heap of size n instead of min-heap of size k — works but is O(n log n), not the required better bound.
  • Sizing the buckets array as buckets.length = k instead of n+1 — a number could appear n times, not k times.
  • Forgetting that the answer can be returned in any order — over-sorting it.

Follow-up questions

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

  • Top K Frequent Words (LC 692) — lexicographic tie-break adds nuance.
  • Track top-K in a sliding window of the last W elements.
  • Distributed top-K — sketch how you'd compute top-K across many shards (count-min sketch / approximate).

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 does bucket sort give O(n) here?

Frequencies are integer counts bounded by the input length n. So you can use indices 0..n directly as buckets, sidestepping the comparison-sort log factor entirely.

Will heap be accepted instead of bucket sort?

Usually yes, because O(n log k) is strictly better than O(n log n) when k << n — but a strict reading of the problem demands true sub-n log n. Robinhood interviewers often follow up with 'can you do it in O(n)?' if you don't volunteer the bucket trick.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →