Skip to main content

347. Top K Frequent Elements

mediumAsked at Anduril

Return the k most frequently occurring integers in an array. Anduril asks this to test whether you know the O(n) bucket-sort approach versus the O(n log k) heap — the same frequency-ranking logic drives mission-critical log triage and alert deduplication in real-time systems.

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

Source citations

Public interview reports confirming this problem appears in Anduril loops.

  • Glassdoor (2026-Q1)— Reported in Anduril SWE onsite threads as a frequency-analysis medium question.
  • Blind (2025-12)— Multiple Anduril candidate posts list Top K Frequent Elements as a high-signal medium in technical rounds.

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 — both in the top 2.

Example 2

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

Explanation: Only one element.

Approaches

1. Min-heap of size k

Count frequencies with a map. Maintain a min-heap of size k over (frequency, value) pairs. At the end, extract all elements from the heap.

Time
O(n log k)
Space
O(n)
// JS has no built-in heap; simulate with a sort on the frequency map.
// For an actual min-heap, use a library or implement one.
function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);
  // Sort entries by frequency descending, take first k
  return [...freq.entries()]
    .sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map(([val]) => val);
}

Tradeoff: O(n log n) due to full sort. In a real implementation with a size-k min-heap, this would be O(n log k). Mention the heap approach verbally even if simulating with sort in JS.

2. Bucket sort (O(n))

After counting frequencies, create buckets indexed by frequency (1..n). Collect elements from the highest-frequency buckets 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);
  // buckets[i] = list of numbers with frequency i
  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. The key insight: frequencies are bounded by n (an element can appear at most n times), so an array of length n+1 serves as a perfect hash map for frequency → elements. This is the answer Anduril engineers are impressed by.

Anduril-specific tips

Start with the heap approach and state complexity, then immediately offer the bucket-sort upgrade: 'Since frequencies are bounded by n, I can use a frequency array as a hash map and collect from the top in O(n).' Anduril engineers value knowing when a problem has a sub-O(n log n) solution. Mentioning the problem-specific constraint (frequencies bounded by array length) that unlocks the O(n) approach is a strong signal of algorithmic maturity.

Common mistakes

  • Building a full sort of all elements — O(n log n) when O(n log k) heap or O(n) bucket is possible.
  • Bucket array length should be nums.length + 1, not nums.length — a frequency of n is valid for an array of all identical elements.
  • Not handling ties — the problem guarantees a unique answer, but know that ties would require a tiebreaker.
  • Off-by-one when collecting from buckets — start from buckets.length - 1 (index n), not buckets.length.

Follow-up questions

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

  • Top K frequent words (LC 692) — requires lexicographic tiebreaker.
  • Sort characters by frequency (LC 451).
  • How would you maintain top-K frequent elements dynamically as new elements arrive?

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 does the bucket array have length n+1?

An element can appear at most n times (if all elements are identical), so frequencies range from 1 to n. Index 0 is unused.

Is the bucket-sort approach always preferred?

For the static problem yes, but for a streaming version a min-heap of size k is preferable since you can process elements incrementally.

Does the problem guarantee no ties in the top-k?

Yes — 'It is guaranteed that the answer is unique' means ties don't affect which k elements qualify.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →