Skip to main content

347. Top K Frequent Elements

mediumAsked at Linear

Return the k most frequent elements in an array. Linear uses this to probe your knowledge of heaps vs. bucket sort — both O(n log k) and O(n) solutions exist, and the interviewer wants to see if you know both.

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

Source citations

Public interview reports confirming this problem appears in Linear loops.

  • Glassdoor (2025-12)— Mentioned in recent Linear SWE onsite reports as a heap and bucket sort problem.
  • r/cscareerquestions (2025-11)— Cited in Linear interview threads as a medium that tests multiple approaches.

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]

Example 2

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

Approaches

1. Sort by frequency

Count frequencies, sort entries by frequency descending, take the top 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). Clean and readable. Acceptable at Linear but not optimal — name this and pivot to the O(n log k) heap or O(n) bucket solution.

2. Min-heap of size k

Maintain a min-heap capped at k elements — if a new element's frequency exceeds the heap minimum, swap it in.

Time
O(n log k)
Space
O(n)
// JavaScript lacks a built-in heap; show the concept
function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
  // In a real interview, use a priority queue library or implement a min-heap
  // For clarity, simulate with sorted entries:
  return [...freq.entries()]
    .sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map(([num]) => num);
}

Tradeoff: O(n log k) — better than O(n log n) when k << n. In languages with built-in priority queues (Python heapq, Java PriorityQueue), this is the standard solution.

3. Bucket sort (optimal)

Use frequency as the bucket index. Create n+1 buckets (index = frequency), scatter elements, then read from highest to lowest.

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. Frequency is bounded by nums.length, so bucket indices are valid. Avoids sorting entirely — the most impressive solution to arrive at during an interview.

Linear-specific tips

Walk through all three approaches in order: sort (O(n log n)), heap (O(n log k)), bucket (O(n)). Linear interviewers want to see this progression. Even if you only code the bucket sort, you should name the other two and explain when each is practical. The bucket sort insight — 'frequency is bounded by n, so I can use it as an index' — is a key moment to articulate clearly.

Common mistakes

  • Not realizing bucket sort is possible — frequency is bounded, so it's a valid index. Don't assume you need a comparison sort.
  • Off-by-one on bucket array size — you need n+1 buckets (indices 0 through n) since an element can appear up to n times.
  • Returning more than k elements when a bucket has multiple elements and fills the result over k — slice at the end.

Follow-up questions

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

  • Sort Characters By Frequency (LC 451) — same pattern applied to a string.
  • Kth Largest Element in an Array (LC 215) — similar k-selection problem using quickselect.
  • What if k is very large (close to n)? Which approach is best?

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 key domain. Here, frequency is in [1, n], giving us a finite, predictable range to use as array indices.

When should I prefer the heap approach?

When n is very large and k is small, the heap processes only k elements in sorted order, making it more practical than full bucket sort materialization.

Does the order of results matter?

The problem says 'return in any order,' so all three approaches are valid regardless of the output sequence.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →