Skip to main content

347. Top K Frequent Elements

mediumAsked at Glean

Glean loves this problem because top-K selection is literally how search result ranking works — retrieving the K most relevant documents from a frequency-weighted index without sorting all candidates.

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

Source citations

Public interview reports confirming this problem appears in Glean loops.

  • Glassdoor (2026-Q1)— Glean engineers explicitly flag Top K Frequent as a problem that mirrors their internal ranking pipeline design.
  • Blind (2025-11)— Ranked among the top 3 most-cited Glean coding problems due to its direct connection to search ranking.

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 — both in the top 2.

Example 2

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

Explanation: Only one element; it is trivially the most frequent.

Approaches

1. Sort by frequency

Count frequencies with a Map. Sort unique elements by frequency descending. Return the first k.

Time
O(n log 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);
  return [...freq.entries()]
    .sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map(([num]) => num);
}

Tradeoff: O(n log n) — simple to write but the problem's follow-up asks for a sub-O(n log n) solution. Present this first, then optimize.

2. Bucket sort (O(n))

Frequencies range from 1 to n. Create n+1 buckets indexed by frequency. Place each element in its bucket. Scan buckets from high to low and collect k elements.

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--) {
    result.push(...buckets[i]);
  }
  return result.slice(0, k);
}

Tradeoff: O(n) time and space. The bucket index is the frequency, and frequency is bounded by n, so bucket sort applies. This is the optimal solution and what Glean typically pushes toward.

Glean-specific tips

Lead with the O(n log n) sort-by-frequency approach to show you can solve it, then immediately say 'the follow-up is to beat O(n log n) — bucket sort lets us do this in O(n) because frequencies are bounded by n.' Glean interviewers almost always ask for the linear solution. Connecting this to search ranking scores well: 'In a search index, you'd use a heap for online top-K over a stream, or bucket sort for offline batch ranking.'

Common mistakes

  • Sorting nums directly instead of sorting by frequency — irrelevant to which elements are most frequent.
  • Off-by-one on bucket array length — frequencies go up to nums.length, so you need nums.length+1 buckets (index 0 is unused).
  • Using a min-heap of size k — this gives O(n log k) and is valid, but harder to implement in JavaScript without a built-in heap. Mention it but prefer bucket sort.
  • Returning more than k elements — slice to exactly k after collecting from buckets.

Follow-up questions

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

  • Top K Frequent Words (LC 692) — same problem but with strings; requires lexicographic tiebreaking.
  • Kth Largest Element in an Array (LC 215) — use Quickselect for O(n) average-case selection.
  • How would you handle a streaming input where frequencies update dynamically?

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 does bucket sort work here but not in general?

Bucket sort requires a bounded integer key domain. Here, frequencies are integers in [1, n] — bounded by the array length. That bound makes bucket sort applicable.

When would you use a min-heap instead of bucket sort?

When processing a stream where n is unknown (you can't pre-size buckets) or when k << n and you want to keep only k elements in memory. The heap uses O(k) space vs O(n) for bucket sort.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →