Skip to main content

85. Top K Frequent Elements

mediumAsked at Datadog

Return the k most frequent elements. Datadog asks this for the heap-of-size-k + bucket-sort alternative — same shape as their top-K leaderboard for hottest metric series in a high-cardinality stream.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — top-K leaderboard analog.
  • Blind (2025-12)— Recurring at Datadog.

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).

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]

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)
function topKFrequent(nums, k) {
  const c = new Map();
  for (const x of nums) c.set(x, (c.get(x) || 0) + 1);
  return [...c.entries()].sort((a, b) => b[1] - a[1]).slice(0, k).map(e => e[0]);
}

Tradeoff: Violates the better-than-n-log-n requirement.

2. Bucket sort (optimal)

Count frequencies; bucket[freq] = list of values with that freq. Walk buckets high-to-low.

Time
O(n)
Space
O(n)
function topKFrequent(nums, k) {
  const c = new Map();
  for (const x of nums) c.set(x, (c.get(x) || 0) + 1);
  const buckets = Array.from({length: nums.length + 1}, () => []);
  for (const [val, freq] of c) buckets[freq].push(val);
  const out = [];
  for (let f = buckets.length - 1; f >= 0 && out.length < k; f--) for (const v of buckets[f]) {
    out.push(v);
    if (out.length === k) return out;
  }
  return out;
}

Tradeoff: O(n) time, O(n) space. Datadog-canonical: bucket sort is the streaming-aware approach when frequency is bounded by n.

Datadog-specific tips

Datadog will probe: 'Streaming version?' Bucket sort doesn't directly stream — switch to a min-heap of size k (O(n log k)). Articulate both before they ask.

Common mistakes

  • Using a max-heap of size n — works but O(n + k log n), worse than bucket.
  • Forgetting that max bucket index is n (when all elements are identical).
  • Off-by-one — bucket size must be nums.length + 1, not nums.length.

Follow-up questions

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

  • K Closest Points to Origin (LC 973) — same heap pattern.
  • Top K Frequent Words (LC 692) — string variant with lex tiebreak.
  • Datadog-style: streaming top-K leaderboard via min-heap of size k.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Bucket sort or heap?

Bucket: O(n), works when freq is bounded. Heap: O(n log k), streaming-friendly. Datadog accepts both with the tradeoff articulated.

Why size n+1 buckets?

Frequencies range from 1 to n. Index n+1 covers all possible frequencies.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →