Skip to main content

21. Top K Frequent Elements

mediumAsked at Chime

Return the k most frequent elements in an integer array in better-than-O(n log n) time.

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

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).

Constraints

  • 1 <= nums.length <= 10^5
  • k is in the range [1, the number of unique elements].
  • 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. Count then sort

Build a count map, sort entries by count descending, slice the top k. Violates the time bound when n is large.

Time
O(n log n)
Space
O(n)
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(p=>p[0]);

Tradeoff:

2. Bucket sort by frequency

Count occurrences then place each value into a bucket indexed by its frequency. Walk buckets from highest to lowest collecting k values. Linear time.

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, c] of counts) buckets[c].push(val);
  const out = [];
  for (let i = buckets.length - 1; i >= 0 && out.length < k; i--) {
    for (const v of buckets[i]) {
      out.push(v);
      if (out.length === k) break;
    }
  }
  return out;
}

Tradeoff:

Chime-specific tips

Chime asks this in fraud heuristics rounds where the answer is the top-K merchants by velocity; mention the bucket-sort bound up front to signal you have seen the streaming variant.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →