Skip to main content

347. Top K Frequent Elements

mediumAsked at Elastic

Return the k most frequent elements in an array. Elastic asks this because computing top-K term frequencies is at the heart of Elasticsearch's terms aggregation and relevance scoring — and bucket-sort vs. heap trade-offs map directly to how Elasticsearch chooses between different aggregation strategies.

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

Source citations

Public interview reports confirming this problem appears in Elastic loops.

  • Glassdoor (2026-Q1)— Top-K frequency and ranking problems appear consistently in Elastic SWE coding rounds across multiple interview reports.
  • Blind (2025-11)— Elastic candidates specifically note this problem as testing whether you know heap vs. bucket sort — both must be discussable.

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 (most frequent), 2 appears 2 times (second most frequent).

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. Maintain a min-heap of size k. For each element, add it to the heap and pop the minimum if the heap exceeds size k. The heap retains the top-k frequent elements.

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

Tradeoff: O(n log n) due to full sort, but clean for an interview. In production Java/Go code, use an actual min-heap for O(n log k). Mention this explicitly to Elastic interviewers.

2. Bucket sort — O(n)

Create n+1 frequency buckets (index = count). Traverse buckets from high to low, collecting elements until k are found.

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);
  // Buckets indexed by frequency; max frequency <= nums.length
  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--) {
    result.push(...buckets[i]);
  }
  return result.slice(0, k);
}

Tradeoff: O(n) time — optimal. The key insight is that frequency is bounded by n, so bucket indices fit in a fixed-size array. This is the answer that impresses Elastic interviewers.

Elastic-specific tips

Lead with the heap approach to establish correctness, then pivot to bucket sort for the O(n) guarantee. Explicitly say: 'In a real Elasticsearch terms aggregation, the heap approach is used because k is much smaller than n (top-10 terms out of millions). But if k is close to n, bucket sort wins.' This systems-thinking framing is exactly what Elastic values.

Common mistakes

  • Using a max-heap of all elements instead of a min-heap of size k — O(n log n) rather than O(n log k).
  • Off-by-one in bucket-sort array size — use nums.length + 1 so index nums.length is valid (every element is the same).
  • Not collecting all elements from a bucket before checking result.length — a bucket may have multiple elements at the same frequency.
  • Returning frequencies instead of the elements themselves.

Follow-up questions

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

  • Top K Frequent Words (LC 692) — return top-k frequent strings with lexicographic tiebreaking.
  • Sort Characters By Frequency (LC 451) — sort all characters by descending frequency.
  • How does Elasticsearch's terms aggregation use a heap to collect top-K buckets efficiently across shards?

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 use a min-heap instead of a max-heap?

A min-heap of size k lets you quickly evict the least-frequent element when the heap overflows, keeping only the top-k. A max-heap would require popping all n elements to get the top-k.

Why is bucket sort O(n) guaranteed here?

The maximum frequency any element can have is n (if all elements are the same). So the bucket array has at most n+1 slots — bounded by n — and filling it requires one pass over the frequency map.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →