347. Top K Frequent Elements

Q: Why is bucket sort O(n) here but typically O(n + k) elsewhere?

The bucket count is bounded by n (max possible frequency), so bucket creation is O(n). Collecting from the top is at most O(n) across all buckets. No comparison sorts are needed.

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

The algorithm returns all elements, which is correct. The problem guarantees k is within valid range, so no special handling needed.

Q: Can two elements tie on frequency at the boundary of k?

The problem guarantees a unique answer (the top k set is well-defined), so ties at the k boundary won't occur in the given test cases.

mediumAsked at HubSpot

HubSpot asks Top K Frequent Elements to test your knowledge of heap-based selection and bucket sort — patterns that power ranking and analytics features like 'top properties by usage' or 'most engaged contacts' across their marketing platform.

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

Source citations

Public interview reports confirming this problem appears in HubSpot loops.

Glassdoor (2026-Q1)— HubSpot SWE onsite reports cite Top K Frequent Elements as a representative medium-difficulty problem.
Blind (2025-11)— Appears in HubSpot interview experience threads as a test of heap vs. bucket sort trade-offs.

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, 3 appears 1 time. Top 2 are [1, 2].

Example 2

Input

nums = [1], k = 1

Output

[1]

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

Approaches

1. Bucket sort (O(n))

Count frequencies with a hash map. Create n+1 buckets indexed by frequency. Place each number into its frequency bucket. Collect results from the highest-frequency bucket downward until k elements are gathered.

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);
  // buckets[i] = array of numbers with frequency i
  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 — better than the sorting or heap approaches. The insight is that frequency is bounded by n, so bucket sort is applicable. HubSpot interviewers are impressed when you lead with this approach rather than reaching for a heap.

2. Min-heap of size k

Count frequencies, then maintain a min-heap of size k over (frequency, element) pairs. After processing all elements, the heap contains the top k most frequent elements.

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

function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
  // JavaScript doesn't have a built-in heap;
  // convert to sorted array as a practical alternative
  return [...freq.entries()]
    .sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map(([num]) => num);
}

Tradeoff: Sort-based is O(n log n) in JS (no built-in heap). A true min-heap would be O(n log k). The sort approach is acceptable in JS interviews when a heap library isn't available — but always acknowledge the true heap solution exists in Java/Python.

HubSpot-specific tips

Start with the frequency map (always step 1), then explain two paths: 'I can sort in O(n log n), or use bucket sort in O(n) since frequency is bounded by array length.' HubSpot values the bucket sort insight — it shows you think about constraints before reaching for generic data structures. In Java, they'd expect a PriorityQueue; in Python, heapq.nlargest. JavaScript interviews typically accept the sort approach with a mention of heap.

Common mistakes

Creating buckets of size n instead of n+1 — frequency can equal nums.length (all same element); index n must be valid.
Collecting more than k elements and returning without slicing — return exactly k.
Sorting in ascending order and slicing from the wrong end.
Forgetting that multiple elements can share the same frequency — bucket arrays (not single values) handle this correctly.

Follow-up questions

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

Top K Frequent Words (LC 692) — same pattern but lexicographic tiebreaking.
Kth Largest Element in an Array (LC 215) — heap-based selection vs. quickselect.
How would you solve this if elements are inserted in a stream and you query k most frequent at any time?

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 bucket sort O(n) here but typically O(n + k) elsewhere?

The bucket count is bounded by n (max possible frequency), so bucket creation is O(n). Collecting from the top is at most O(n) across all buckets. No comparison sorts are needed.

What if k equals the number of distinct elements?

The algorithm returns all elements, which is correct. The problem guarantees k is within valid range, so no special handling needed.

Can two elements tie on frequency at the boundary of k?

The problem guarantees a unique answer (the top k set is well-defined), so ties at the k boundary won't occur in the given test cases.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →