Skip to main content

347. Top K Frequent Elements

mediumAsked at Bloomberg

Bloomberg's market-intelligence dashboards surface the top-K most actively traded tickers across millions of events per session — this problem tests whether you can identify those leaders in O(n log k) using a min-heap rather than sorting the full frequency table.

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

Problem

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

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 1 <= k <= number of unique elements
  • 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. Full sort on frequency map

Build a frequency map, convert to an array of [element, count] pairs, sort descending by count, slice the top 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(e => e[0]);
}

Tradeoff:

2. Min-heap of size k (optimal)

Build the frequency map, then maintain a min-heap of size k keyed by frequency. Iterate over the map; push each entry and pop when the heap exceeds k. The heap holds exactly the top-k elements in O(n log k).

Time
O(n log k)
Space
O(n)
class MinHeap {
  constructor() { this.data = []; }
  push([el, cnt]) {
    this.data.push([el, cnt]);
    this._up(this.data.length - 1);
  }
  pop() {
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length) { this.data[0] = last; this._down(0); }
    return top;
  }
  size() { return this.data.length; }
  _up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.data[i][1] < this.data[p][1]) {
        [this.data[i], this.data[p]] = [this.data[p], this.data[i]]; i = p;
      } else break;
    }
  }
  _down(i) {
    const n = this.data.length;
    while (true) {
      let s = i, l = 2*i+1, r = 2*i+2;
      if (l < n && this.data[l][1] < this.data[s][1]) s = l;
      if (r < n && this.data[r][1] < this.data[s][1]) s = r;
      if (s === i) break;
      [this.data[i], this.data[s]] = [this.data[s], this.data[i]]; i = s;
    }
  }
}

function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
  const heap = new MinHeap();
  for (const entry of freq.entries()) {
    heap.push(entry);
    if (heap.size() > k) heap.pop();
  }
  return heap.data.map(e => e[0]);
}

Tradeoff:

Bloomberg-specific tips

Bloomberg typically follows this up with a streaming variant: 'what if the array is too large to fit in memory?' The min-heap approach shines there because you process one chunk at a time and merge intermediate heaps — the same pattern Bloomberg uses for distributed top-K across partitioned market-data feeds. Mention that proactively; it shows you think beyond the local algorithm to the distributed systems context Bloomberg cares about.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →