Skip to main content

347. Top K Frequent Elements

mediumAsked at eBay

eBay's search team computes the top-K most searched items, trending product categories, and popular sellers in real time. Top K Frequent Elements is the canonical algorithm interview version. The key insight is that a min-heap of size k is faster than full sorting when k is small — a distinction eBay senior engineers look for.

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

Source citations

Public interview reports confirming this problem appears in eBay loops.

  • Glassdoor (2026-Q1)— Cited as a common eBay medium problem testing heap usage and frequency counting.
  • Blind (2025-11)— eBay SWE threads list Top K Frequent Elements as a high-probability medium question for mid-to-senior candidates.

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 — these are the top 2.

Example 2

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

Explanation: Only one element.

Approaches

1. Frequency map + sort

Count frequencies with a Map, then sort entries by frequency descending and return the first k keys.

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(([val]) => val);
}

Tradeoff: O(n log n) — simple and readable. Fine when n and k are similar in magnitude, but sub-optimal when k << n.

2. Bucket Sort (O(n))

Create an array of n+1 buckets where bucket[i] holds numbers that appear exactly i times. Collect from the highest bucket down 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 [val, count] of freq) buckets[count].push(val);
  const result = [];
  for (let i = buckets.length - 1; i >= 1 && result.length < k; i--) {
    result.push(...buckets[i]);
  }
  return result.slice(0, k);
}

Tradeoff: O(n) time — optimal. Bucket index = frequency, so maximum bucket index = nums.length. Elegant and avoids sorting entirely. This is the answer that impresses eBay interviewers who ask for better than O(n log n).

eBay-specific tips

eBay interviewers often explicitly ask 'can you do better than O(n log n)?' — that's the cue for bucket sort. The insight: frequency is bounded by n, so you can use the frequency as an array index. Mention this optimization proactively if the interviewer hasn't asked. Also mention the heap approach (O(n log k)) as a middle ground when n is large but memory for buckets is constrained.

Common mistakes

  • Off-by-one on bucket array size — max frequency is nums.length (all elements the same), so buckets needs length nums.length + 1.
  • Returning more than k elements when a bucket contains multiple values — use slice(0, k) on the result.
  • Sorting the Map entries in ascending order and taking the last k — this works but is less readable than descending sort.
  • Assuming k == 1 returns a single value, not an array — the problem always returns an array.

Follow-up questions

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

  • Top K Frequent Words (LC 692) — same idea but with lexicographic tiebreaking.
  • Sort Characters By Frequency (LC 451) — reconstruct a string sorted by character frequency.
  • How would you maintain the top-K frequent elements in a live data stream without recomputing from scratch?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

When should I use a heap instead of bucket sort?

When frequency is not bounded by n — e.g., timestamps in a stream. A min-heap of size k runs in O(n log k) and works on unbounded frequency values.

Why is bucket sort O(n) here?

Frequency values are bounded by nums.length (n), so the bucket array has O(n) slots and the scan is O(n). No comparison-based sort is needed.

What if there are ties in frequency?

The problem guarantees a unique answer (no ties affecting the top-k boundary), so you don't need tiebreaking logic here. For Top K Frequent Words (LC 692), ties break by lexicographic order.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →