347. Top K Frequent Elements

Q: When is the heap (O(n log k)) approach better than bucket sort (O(n))?

When k is much smaller than n, log k is small, and heap uses less memory than the full frequency map + n+1 buckets. But for a general interview, bucket sort demonstrates a deeper insight.

Q: Why n+1 buckets instead of n?

An element can appear exactly n times (if all elements are the same), so bucket[n] must be valid — requiring length n+1.

Q: Is the output order guaranteed?

The problem says any order is valid. The bucket-sort approach returns elements in frequency-descending order, which is a nice bonus.

mediumAsked at HP

HP support and diagnostics tools rank error codes and telemetry events by frequency to surface the most impactful hardware failures. Top K Frequent Elements tests whether you can combine frequency counting with an efficient selection mechanism — a pattern used across HP's observability stack.

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

Source citations

Public interview reports confirming this problem appears in HP loops.

Glassdoor (2026-Q1)— HP SWE interviews include Top K Frequent Elements as a medium problem testing heap and bucket-sort knowledge.
Blind (2025-11)— HP technical interview prep threads cite this as a common question for both systems and data-engineering roles.

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 (most frequent), 2 appears 2 times (second most frequent).

Example 2

Input

nums = [1], k = 1

Output

[1]

Explanation: Only one element — it is the most frequent.

Approaches

1. Frequency map + sort

Count frequencies in a map. Sort unique elements by frequency descending. Return the first 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: Simple but O(n log n). Mention this first then optimize if the interviewer asks for better than O(n log n).

2. Bucket sort (O(n))

Create buckets indexed by frequency (bucket[f] = list of numbers with frequency f). Frequency can't exceed n, so there are at most n buckets. Collect k results from the highest-frequency buckets down.

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);
  // bucket[i] = numbers that appear exactly i times
  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 >= 1 && result.length < k; i--) {
    result.push(...buckets[i]);
  }
  return result.slice(0, k);
}

Tradeoff: O(n) time and space — beats O(n log n). The key insight is that frequency is bounded by n, so bucket indices are bounded. HP interviewers reward this insight.

HP-specific tips

HP interviewers frequently ask 'can you do better than O(n log n)?' — be ready to present the bucket-sort approach. Explain the frequency bound clearly: 'In an array of n elements, no element can appear more than n times, so buckets of size n+1 are sufficient.' For systems contexts, note that a min-heap of size k gives O(n log k), which is useful when k is much smaller than n.

Common mistakes

Using full sort when a heap of size k suffices — O(n log k) is better when k << n.
Creating buckets of size n instead of n+1 — frequency n is valid (all elements the same); off-by-one causes an index error.
Not collecting results from high buckets downward — you need the top k, so iterate from the highest frequency bucket.
Forgetting that multiple elements can share the same frequency — buckets hold lists, not single elements.

Follow-up questions

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

What if elements can be added or removed dynamically — maintain a live top-k list.
Find the k least frequent elements instead of most frequent.
How would you implement this for a continuous stream of data with a sliding window?

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 is the heap (O(n log k)) approach better than bucket sort (O(n))?

When k is much smaller than n, log k is small, and heap uses less memory than the full frequency map + n+1 buckets. But for a general interview, bucket sort demonstrates a deeper insight.

Why n+1 buckets instead of n?

An element can appear exactly n times (if all elements are the same), so bucket[n] must be valid — requiring length n+1.

Is the output order guaranteed?

The problem says any order is valid. The bucket-sort approach returns elements in frequency-descending order, which is a nice bonus.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →