Skip to main content

14. Top K Frequent Elements

mediumAsked at JetBrains

Return the k most frequent elements — JetBrains uses this to test bucket-sort intuition behind their frequency-based identifier ranking.

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, and the answer is guaranteed to be unique.

Constraints

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

Build a frequency map, sort entries by frequency, slice the first k.

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

Tradeoff:

2. Bucket sort by frequency

Counts max out at n, so place values into buckets indexed by frequency and walk from high to low. Linear time, no comparison sort. JetBrains values this pattern for symbol-popularity ranking.

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 [n, c] of freq) buckets[c].push(n);
  const out = [];
  for (let i = buckets.length - 1; i >= 0 && out.length < k; i--) out.push(...buckets[i]);
  return out.slice(0, k);
}

Tradeoff:

JetBrains-specific tips

JetBrains expects you to spot the bounded-count trick — IDE identifier-popularity ranking uses bucketed frequencies for the same reason: linear time, predictable budget.

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 JetBrains interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →