Skip to main content

347. Top K Frequent Elements

mediumAsked at Akamai

Return the k most frequent elements in an array. Akamai frames this as a real edge-analytics problem: finding the top K most requested URLs from billions of daily log events. The heap vs. bucket-sort trade-off maps directly to what's feasible in streaming vs. batch pipelines.

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

Source citations

Public interview reports confirming this problem appears in Akamai loops.

  • Glassdoor (2026-Q1)— Akamai SWE candidates report Top K Frequent Elements as a common heap and frequency-counting question.
  • Blind (2025-11)— Akamai interview threads cite this as a high-signal medium problem connecting heaps to real analytics scenarios.

Problem

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. It is guaranteed that the answer is unique.

Constraints

  • 1 <= nums.length <= 10^5
  • −10^4 <= nums[i] <= 10^4
  • k is in the range [1, the number of unique elements in nums].
  • 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 — top 2.

Example 2

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

Explanation: Single element is trivially the most frequent.

Approaches

1. Frequency map + sort

Count frequencies with a Map, then sort entries by frequency descending and take 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(([val]) => val);
}

Tradeoff: O(n log n). Simple, but sorting all unique elements when only k are needed is wasteful. Offer this as the baseline, then show the O(n) bucket approach.

2. Bucket sort (O(n))

Create an array of n+1 buckets indexed by frequency. Place each element in the bucket matching its frequency. Scan buckets from highest to lowest to collect the top k.

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] = list of numbers with frequency i
  const bucket = Array.from({ length: nums.length + 1 }, () => []);
  for (const [num, count] of freq) bucket[count].push(num);
  const result = [];
  for (let i = bucket.length - 1; i >= 0 && result.length < k; i--) {
    result.push(...bucket[i]);
  }
  return result.slice(0, k);
}

Tradeoff: O(n) time and space — beats sorting. The maximum possible frequency is n (all elements identical), so the bucket array is bounded at n+1 elements. This is the optimal solution.

Akamai-specific tips

Start with the sort-based solution to establish correctness, then say: 'The constraint asks for better than O(n log n). Since frequencies range from 1 to n, I can use bucket sort — an O(n) approach.' Akamai asks the follow-up about O(n log k) heap solutions for streaming contexts where n is infinite; acknowledge the trade-off between batch (bucket sort) and streaming (min-heap of size k).

Common mistakes

  • Forgetting that bucket indices go up to nums.length, not the number of unique elements — the max frequency is the full array length.
  • Returning more than k elements when a bucket has multiple elements — slice at the end to enforce the exact k count.
  • Using a max-heap in JavaScript — JS has no built-in priority queue; if using a heap-based approach, implement one explicitly.

Follow-up questions

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

  • Kth Largest Element in an Array (LC 215) — similar k-selection problem using Quickselect.
  • How would you solve this in a streaming setting where nums arrives element by element and n is unknown?
  • Sort Characters By Frequency (LC 451) — sort all characters by frequency rather than selecting top 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

When would you use a min-heap of size k instead of bucket sort?

In a streaming context where n is unknown or infinite. A min-heap of size k maintains the top k in O(log k) per insert, requiring only O(k) space. Bucket sort requires knowing the max frequency upfront, which assumes a fixed finite input.

Why bucket[nums.length + 1] and not bucket[max_freq + 1]?

To avoid a separate pass to find max_freq. nums.length is a known upper bound on any frequency, so it is always safe.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →