Skip to main content

22. Top K Frequent Elements

mediumAsked at Monzo

Return the k merchant categories that appear most often in a customer's spending feed.

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, number of unique elements]

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

Tally frequencies in a map, then sort entries by frequency descending and take the first k.

Time
O(n log n)
Space
O(n)
const m = new Map();
for (const x of nums) m.set(x, (m.get(x) || 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

Frequencies are bounded by n; bucket numbers by their count and walk buckets from high to low until k are collected.

Time
O(n)
Space
O(n)
function topKFrequent(nums, k) {
  const freq = new Map();
  for (const x of nums) freq.set(x, (freq.get(x) || 0) + 1);
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [v, c] of freq) buckets[c].push(v);
  const out = [];
  for (let i = buckets.length - 1; i >= 0 && out.length < k; i--) for (const v of buckets[i]) { if (out.length < k) out.push(v); }
  return out;
}

Tradeoff:

Monzo-specific tips

Monzo expects you to point out that automatic categorization needs frequency tallies on hot paths, so the linear bucket approach is the production move.

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

Practice these live with InterviewChamp.AI →