Skip to main content

347. Top K Frequent Elements

mediumAsked at Broadcom

Find the k most frequent elements in an array in better than O(n log n) time. Broadcom asks this because frequency-based ranking is fundamental to hot-flow identification in network traffic analysis — a core operation in Broadcom's telemetry and switching software.

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

Source citations

Public interview reports confirming this problem appears in Broadcom loops.

  • Glassdoor (2026-Q1)— Mentioned in Broadcom SWE onsite reports as a heap vs bucket-sort trade-off question.
  • Blind (2025-09)— Broadcom threads cite Top K Frequent as a medium problem that tests knowledge of heap, bucket sort, and QuickSelect.

Problem

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. The answer is guaranteed to be 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 nums].
  • 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 twice — both are in the top 2.

Example 2

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

Explanation: Only one element.

Approaches

1. Min-heap of size k

Build a frequency map. Maintain a min-heap of size k over (frequency, element) pairs. After processing all elements, the heap contains the k most frequent.

Time
O(n log k)
Space
O(n)
function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
  // Simulate min-heap with sorted array (JS has no built-in heap)
  const entries = [...freq.entries()].sort((a, b) => b[1] - a[1]);
  return entries.slice(0, k).map(e => e[0]);
}

Tradeoff: The sort is O(n log n) in JS (since there's no built-in heap). In a heap-aware language like Java/Go, this is O(n log k). Explain the heap approach conceptually even if coding in JS.

2. Bucket sort (O(n))

Create an array of buckets indexed by frequency (0 to n). Place each element in its frequency bucket. Collect elements from the highest-frequency buckets 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);
  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 sort-based approach. The bucket index is bounded by nums.length since no element can appear more than n times. This is the approach that satisfies the problem's 'better than O(n log n)' requirement.

Broadcom-specific tips

At Broadcom, articulate both approaches and why bucket sort hits O(n): 'The maximum frequency is bounded by n, so I can use frequency as an array index — that's the key insight.' Then connect to domain: 'Top-k hot flows in switch telemetry is exactly this problem at scale — you want O(n) frequency counting, not a sort.' Broadcom interviewers appreciate QuickSelect as a third mention (O(n) average) if time permits.

Common mistakes

  • Using sort without noting it's O(n log n) — the problem asks for better than that.
  • Off-by-one in bucket array size — frequencies range from 1 to n, so the array needs n+1 slots.
  • Not handling duplicate frequencies in the bucket approach — multiple elements can share a frequency.
  • Returning too many elements when a bucket has more than needed — slice to exactly k.

Follow-up questions

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

  • Top K Frequent Words (LC 692) — adds lexicographic tie-breaking.
  • Kth Largest Element in an Array (LC 215) — QuickSelect approach.
  • How would you solve this on a stream of integers without storing all of them (Count-Min Sketch)?

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 O(n)?

Both the frequency-map build and the bucket scan are O(n). The bucket array size is n+1 — bounded by input length, not element value.

When would you prefer a heap over bucket sort?

When the input is a continuous stream and you can't know n in advance. A heap of size k processes each element in O(log k) and works online.

What is QuickSelect?

A partition-based selection algorithm averaging O(n) time. It finds the kth largest element without full sorting. Mention it as an alternative but implement bucket sort in a JS interview.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →