Skip to main content

347. Top K Frequent Elements

mediumAsked at Pinterest

Pinterest's recommendation infrastructure runs top-K queries everywhere: trending pins, top boards by engagement, most-clicked categories. Top K Frequent Elements asks you to return the K most-frequent numbers; the interviewer wants either the heap or bucket-sort solution depending on the input shape.

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

Source citations

Public interview reports confirming this problem appears in Pinterest loops.

  • Glassdoor (2026-Q1)— Pinterest backend / recsys onsite reports cite Top K Frequent as the data-structures round for ML-infra-adjacent SWEs.
  • LeetCode Pinterest tag (2026-Q1)— Listed on the Pinterest company-tagged problem list as a high-frequency entry.
  • Reddit r/cscareerquestions (2025-12)— Pinterest L4 onsite reports describe this as a 35-minute heap question with a 'top-N trending' framing.

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 the array].
  • Your algorithm's time complexity must be better than O(n log n).

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. Frequency map + sort (brute force)

Count frequencies, sort entries by frequency descending, return the top K.

Time
O(n log n)
Space
O(n)
function topKFrequentBrute(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(([n]) => n);
}

Tradeoff: Simple but violates the better-than-O(n log n) constraint stated in the problem. Mention it as the baseline, then move to a heap or bucket sort.

2. Min-heap of size K

Build frequency map. Walk entries; maintain a min-heap of size K. If heap.size > K, pop the smallest. Result is the heap contents.

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

function topKFrequentHeap(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();
  }
  const out = [];
  while (heap.size()) out.push(heap.pop()[0]);
  return out;
}

Tradeoff: O(n log k) — strictly better than full sort when k << n. The bounded heap is the production pattern Pinterest uses for trending-K queries.

3. Bucket sort by frequency (optimal O(n))

Build frequency map. Index a bucket array by frequency (0..n). Walk buckets from high to low, collecting elements until you have 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);
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [num, count] of freq.entries()) buckets[count].push(num);
  const out = [];
  for (let f = buckets.length - 1; f >= 0 && out.length < k; f--) {
    for (const num of buckets[f]) {
      out.push(num);
      if (out.length === k) return out;
    }
  }
  return out;
}

Tradeoff: True O(n) — the most elegant answer. Works because max frequency is bounded by nums.length. This is the answer to volunteer if the interviewer presses on the O(n log k) heap.

Pinterest-specific tips

Pinterest interviewers run a two-stage signal here: first they grade the O(n log k) heap (production-shaped for streaming top-K) and then they ask 'can you do better than n log k?' That's your cue for the bucket-sort answer. Don't lead with bucket-sort — leading with the heap shows you know the production pattern.

Common mistakes

  • Using a max-heap of all elements then popping K times — that's O(n log n), violating the constraint.
  • Forgetting that the bucket index is the frequency, not the element value.
  • Buckets array off-by-one: max possible frequency is nums.length, so array size must be nums.length + 1.
  • Returning entries instead of just the element values.

Follow-up questions

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

  • Streaming: elements arrive one at a time; maintain the top K with each arrival.
  • Top K Frequent Words (LeetCode 692) — adds lexicographic tie-breaking, changes the heap comparator.
  • Distributed top K across N machines — partial top-K-per-machine, then merge.
  • Approximate top K with bounded memory (Count-Min Sketch).

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 is the heap version popular if bucket-sort is O(n)?

Bucket-sort only works when you can bound max frequency. For streaming or distributed scenarios where you don't see all data at once, the bounded heap is the production pattern.

Does Pinterest expect me to implement my own heap?

JavaScript doesn't have a built-in priority queue, so yes — at least the push/pop/peek. Interviewers know this and either accept a comment ('assume a standard MinHeap') or want you to inline it cleanly.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →