347. Top K Frequent Elements

Q: Why is the bucket-sort approach O(n)?

Counting frequencies is O(n). Building and reading buckets is O(n) (at most n unique elements, each placed once). No sorting or heap operations are needed.

Q: What if k equals the number of unique elements?

You return all unique elements. The bucket walk collects everything before the loop ends — correct.

Q: Can Quick Select solve this problem?

Yes — O(n) average using the nth_element pattern on the frequency map entries. Comparable to bucket sort but with O(n) worst-case risk unless you use median-of-medians.

mediumAsked at Gusto

Return the k most frequent elements. Gusto asks this to test frequency counting combined with efficient selection — they want to hear about bucket sort to get O(n) rather than defaulting to heap-sort at O(n log k).

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in Gusto loops.

Glassdoor (2025-11)— Reported in Gusto SWE onsite reports as a medium problem with a follow-up asking for an O(n) solution.
Blind (2025-09)— Gusto interview threads recommend preparing the bucket-sort approach to beat the heap solution on time complexity.

Problem

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. It is guaranteed that the answer is unique.

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 given input].
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. The top 2 are [1, 2].

Example 2

Input

nums = [1], k = 1

Output

[1]

Explanation: Single element is trivially the most frequent.

Approaches

1. Frequency map + bucket sort (O(n))

Count frequencies. Create an array of buckets indexed by frequency (max freq = n). Walk buckets from high to low, collecting elements until you have k.

Time: O(n)
Space: O(n)

function topKFrequent(nums, k) {
  // step 1: count frequencies
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);

  // step 2: bucket by frequency (index = frequency, value = list of nums)
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [num, count] of freq) {
    buckets[count].push(num);
  }

  // step 3: collect top-k from highest frequency buckets
  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. Bucket-sort avoids the O(log n) heap overhead. The max possible frequency is n (all elements the same), so the bucket array has at most n+1 entries.

2. Frequency map + min-heap (O(n log k))

Count frequencies, then maintain a min-heap of size k. Push each element; if the heap exceeds size k, evict the minimum-frequency element.

Time: O(n log k)
Space: O(n + k)

// JavaScript doesn't have a built-in heap — sketch with sorted array for clarity
function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);
  // Sort entries by frequency descending and take first k
  return [...freq.entries()]
    .sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map(([num]) => num);
}

Tradeoff: O(n log n) with sort (O(n log k) with a proper heap). Simpler to implement in JS where heaps aren't built-in. Good baseline to start with before proposing the bucket-sort optimisation.

Gusto-specific tips

Start with the sort/heap approach, then proactively say 'I can do this in O(n) with bucket sort — want me to?' That transition signals algorithmic depth. Gusto also appreciates the observation that bucket index equals frequency, so the bucket array size is bounded by the input length, not 10^4.

Common mistakes

Creating a bucket array of size 10^4 (max element value) instead of n+1 (max frequency) — wrong dimension.
Walking buckets from low to high and reversing at the end — just walk from high to low.
Forgetting that multiple elements can share the same frequency and belong in the same bucket.
Returning more than k elements when a bucket contributes extras — slice to exactly k.

Follow-up questions

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

Top K Frequent Words (LC 692) — break frequency ties alphabetically.
Sort Characters By Frequency (LC 451) — sort a string by character frequency.
What is the minimum k such that all top-k elements together cover more than half the array?

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 is the bucket-sort approach O(n)?

Counting frequencies is O(n). Building and reading buckets is O(n) (at most n unique elements, each placed once). No sorting or heap operations are needed.

What if k equals the number of unique elements?

You return all unique elements. The bucket walk collects everything before the loop ends — correct.

Can Quick Select solve this problem?

Yes — O(n) average using the nth_element pattern on the frequency map entries. Comparable to bucket sort but with O(n) worst-case risk unless you use median-of-medians.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →