Skip to main content

347. Top K Frequent Elements

mediumAsked at Airbnb

Given an integer array and integer k, return the k most frequent elements. Airbnb asks this to test whether you reach for bucket sort or a min-heap — both beat the naive sort.

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

Source citations

Public interview reports confirming this problem appears in Airbnb loops.

  • Glassdoor (2026-Q1)— Airbnb L4 onsite reports list this as a recurring heap medium.
  • Blind (2025-12)— Recurring in Airbnb backend interview reports.

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
  • -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. Sort by frequency (baseline)

Build a frequency map, sort unique elements by frequency descending, take the first k.

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

Tradeoff: Doesn't meet the better-than-O(n log n) requirement. Mention before pivoting.

2. Min-heap of size k

Build frequency map. Push entries into a min-heap; when size exceeds k, pop. The heap holds the top k.

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

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

Tradeoff: O(n log k) beats O(n log n) when k is small. Cleaner than bucket sort if you've already implemented the heap.

3. Bucket sort by frequency (optimal in practice)

Build a frequency map. Create buckets[freq] -> list of nums with that frequency. Walk buckets from highest freq to lowest, taking the first k.

Time
O(n)
Space
O(n)
function topKFrequentBucket(nums, k) {
  const count = new Map();
  for (const x of nums) count.set(x, (count.get(x) || 0) + 1);
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [num, freq] of count) buckets[freq].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) break; }
  }
  return result;
}

Tradeoff: Linear time because each unique element appears in exactly one bucket. Wins when k is close to n; both work.

Airbnb-specific tips

Airbnb's bar is naming the better-than-n-log-n requirement and choosing accordingly. Heap is the safer interview answer because it generalizes; bucket sort is cleaner if you spot that frequencies are bounded by n. Either way, articulate WHY you chose your approach.

Common mistakes

  • Sorting the entire frequency map (O(n log n)) and not meeting the time bound.
  • Using a max-heap of size n instead of a min-heap of size k.
  • In bucket sort, buckets need to be of size n+1 (max possible freq is n).

Follow-up questions

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

  • Top K Frequent Words (LC 692) — strings instead of ints, with lexicographic tie-break.
  • K Closest Points to Origin (LC 973) — same heap pattern.
  • Kth Largest Element in an Array (LC 215) — quickselect O(n) average.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Heap or bucket — which does Airbnb prefer?

Both pass with clear narration. Heap is the more reusable template; bucket sort is the 'clever O(n)' answer when frequencies are bounded.

Why log k and not log n in the heap version?

The heap holds at most k elements at all times. Push/pop on a k-heap is log k. We do that n times -> O(n log k).

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →