Skip to main content

85. Top K Frequent Elements

mediumAsked at Workday

Return the k most frequent elements in an array. Workday uses this for bucket-sort vs heap decisions — same shape as 'top-k most-used permission codes across an org'.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2026-Q1)— Workday SDE2 phone screen.

Problem

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • k is in the range [1, the number of unique elements].
  • It is guaranteed that the answer is unique.

Examples

Example 1

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

Example 2

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

Approaches

1. Sort by frequency

Count, sort entries by count desc, take first k.

Time
O(n log n)
Space
O(n)
// fails the better-than-n-log-n requirement

Tradeoff: Violates the complexity constraint.

2. Bucket sort by frequency

Count frequencies. Create buckets indexed by count. Walk from high count down, collecting k values.

Time
O(n)
Space
O(n)
function topKFrequent(nums, k) {
  const freq = new Map();
  for (const x of nums) freq.set(x, (freq.get(x) || 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--) {
    for (const num of buckets[i]) {
      result.push(num);
      if (result.length === k) return result;
    }
  }
  return result;
}

Tradeoff: Bucket sort works because max frequency is bounded by n. O(n) time, O(n) space.

Workday-specific tips

Workday wants bucket sort, not a heap. State that max frequency is bounded by n, which is why bucketing works. Heap version (O(n log k)) is acceptable but the bucket version is sharper.

Common mistakes

  • Using sort — violates the constraint.
  • Min-heap of size k — works but O(n log k), not strictly < n log n.
  • Off-by-one on bucket array size (must be n + 1 to hold a count of n).

Follow-up questions

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

  • Sort Characters By Frequency (LC 451) — same bucket-sort.
  • Top K Frequent Words (LC 692) — string version with lexicographic tiebreak.
  • K Closest Points to Origin (LC 973).

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 bucket sort works?

Max frequency of any value is bounded by n. We have at most n+1 distinct counts (0 to n). Bucketing by count then walking high-to-low is O(n).

Heap alternative?

Min-heap of size k — O(n log k). Acceptable answer; bucket sort is strictly better at O(n).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →