Skip to main content

347. Top K Frequent Elements

mediumAsked at Amazon

Given an array of numbers and integer k, return the k most frequent elements. Amazon asks this to test whether you reach for bucket sort or heap and can articulate the n log k vs O(n) tradeoff.

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

Source citations

Public interview reports confirming this problem appears in Amazon loops.

  • Glassdoor (2026-Q1)— Amazon SDE I/II onsite reports cite this as a recurring hash + heap problem.
  • Blind (2025-12)— Recurring Amazon interview question.

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. Hash + sort

Count occurrences. Sort entries by count descending. Take top k.

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

Tradeoff: Easy to write. Mention before offering the better solutions.

2. Min-heap of size k

Count, then push each (count, val) onto a min-heap. Pop when size > k. Result is the heap contents.

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() { if (!this.data.length) return; 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) { while (true) { const l = 2*i+1, r = 2*i+2; let best = i; if (l < this.data.length && this.data[l][0] < this.data[best][0]) best = l; if (r < this.data.length && 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 counts = new Map();
  for (const n of nums) counts.set(n, (counts.get(n) || 0) + 1);
  const heap = new MinHeap();
  for (const [val, cnt] of counts) {
    heap.push([cnt, val]);
    if (heap.size() > k) heap.pop();
  }
  return heap.data.map(x => x[1]);
}

Tradeoff: Better than sort when k << n. Common interview answer.

3. Bucket sort (optimal)

Count occurrences. Place each value into a bucket indexed by its count. Walk buckets from highest count down, collecting until k items.

Time
O(n)
Space
O(n)
function topKFrequent(nums, k) {
  const counts = new Map();
  for (const n of nums) counts.set(n, (counts.get(n) || 0) + 1);
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [val, cnt] of counts) buckets[cnt].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: True O(n) because counts are bounded by n. Bucket sort works because counts are integers in [1, n] — no comparison sorting needed.

Amazon-specific tips

Amazon interviewers grade this on whether you can articulate three approaches and pick. State out loud: 'Sort is O(n log n). Min-heap of size k is O(n log k). Bucket sort is O(n) because counts are bounded.' Then pick. Bucket sort is the highest-bar answer; heap is the most-common.

Common mistakes

  • Building a max-heap and popping k times — works but is O(n + k log n), not O(n log k).
  • Forgetting that counts are in [1, n] — bucket size = nums.length + 1.
  • Using O(n^2) brute-force per query when k is small (not the actual ask).

Follow-up questions

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

  • Top K Frequent Words (LC 692) — adds a lexicographic tiebreaker.
  • K Closest Points to Origin (LC 973) — same heap/quickselect pattern.
  • What if the array is a stream?

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 work here?

Counts are integers in [1, n]. Bucket sort works when keys are bounded integers — no comparison sorting needed.

Heap or bucket sort — which is preferred?

Bucket sort scores higher (O(n) vs O(n log k)). Heap is more general (works for any comparable type) — lead with heap, then offer bucket sort if asked for O(n).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →