Skip to main content

347. Top K Frequent Elements

mediumAsked at AMD

Return the k most frequent elements from an array. AMD asks this to probe heap vs bucket-sort trade-offs — the same decision appears when ranking the most-used GPU kernels, hottest cache lines, or most-frequent instruction patterns in a profile-guided optimization pass.

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

Source citations

Public interview reports confirming this problem appears in AMD loops.

  • Glassdoor (2026-Q1)— AMD SWE candidates cite Top K Frequent Elements in medium-round coding sessions, often with a follow-up on time complexity.
  • Blind (2025-09)— AMD interview threads list this as a heap/bucket-sort problem that tests algorithmic trade-off reasoning.

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.

Example 2

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

Explanation: Only one element.

Approaches

1. Min-Heap of size k

Count frequencies with a map. Push elements into a min-heap of size k — evict the minimum-frequency element when the heap exceeds k. The heap retains the k most frequent elements.

Time
O(n log k)
Space
O(n + k)
function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
  // JS lacks a built-in heap; simulate with sorted entries for clarity
  const entries = [...freq.entries()].sort((a, b) => b[1] - a[1]);
  return entries.slice(0, k).map(([num]) => num);
}

Tradeoff: The sort approximates a heap. In a language with a real min-heap (Java PriorityQueue, C++ priority_queue), this would be O(n log k). With sort it's O(n log n). Mention this distinction to AMD interviewers.

2. Bucket Sort

Use frequency as index into a bucket array of length n+1. Each bucket holds all numbers with that frequency. Scan from high to low frequency collecting k results.

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]) {
      if (result.length < k) result.push(num);
    }
  }
  return result;
}

Tradeoff: O(n) — better than O(n log k). Bucket sort works because frequency is bounded by n, so the bucket array has a known finite size. This is the optimal approach.

AMD-specific tips

AMD performance engineers rank hot kernels, hot cache lines, and frequent instruction patterns constantly. Bucket sort is O(n) and exploits the bounded domain of frequencies (max frequency = n) — a property that comes directly from the input size. Make this connection explicit: 'the bucket array size is bounded by n because no element can appear more than n times, so we get a linear-time sort.' AMD interviewers reward this kind of domain-aware optimization.

Common mistakes

  • Using a full sort O(n log n) without mentioning the O(n) bucket-sort alternative.
  • In bucket sort, allocating n+1 slots (indices 0..n) vs n slots — frequency can be exactly n for a single repeated element.
  • Not handling ties within a bucket — when multiple elements share the same frequency, any of them can be selected.
  • Returning frequencies instead of the elements themselves.

Follow-up questions

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

  • Top K Frequent Words (LC 692) — same problem but for strings with lexicographic tiebreaking.
  • Kth Largest Element in an Array (LC 215) — quickselect O(n) average.
  • How would you find the top-k hottest GPU kernel IDs from a profile stream in real time?

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) possible here?

The frequency of any element is at most n (if all elements are the same). So buckets indexed by frequency are bounded by n, giving a constant-time sort relative to the bucket count.

When would you use the heap approach over bucket sort?

When the domain of values is unbounded or very large (e.g., real-valued frequencies), bucket sort doesn't apply. The heap approach generalizes to arbitrary orderings.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →