Skip to main content

347. Top K Frequent Elements

mediumAsked at Shopify

Shopify asks Top K Frequent Elements because 'top K best-selling products', 'top K search queries', and 'top K traffic sources' are bread-and-butter analytics. The interviewer wants you to choose between heap and bucket sort and articulate the tradeoff.

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

Source citations

Public interview reports confirming this problem appears in Shopify loops.

  • Glassdoor (2026-Q1)— Shopify Backend Developer + Engineering Lead onsites cite Top K Frequent as a recurring medium-round.
  • Reddit r/cscareerquestions (2025-11)— Shopify new-grad + intern reports include Top K Frequent with a follow-up about streaming inputs.

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), where n is the array's size.

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. Brute-force sort frequencies

Count with a Map, push entries into an array, sort by frequency descending, take first k.

Time
O(n log n)
Space
O(n)
function topKFrequentSort(nums, k) {
  const count = new Map();
  for (const n of nums) count.set(n, (count.get(n) || 0) + 1);
  return Array.from(count.entries())
    .sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map(([num]) => num);
}

Tradeoff: Simple and short but violates the 'better than O(n log n)' constraint. Mention it explicitly so the interviewer hears you saw it; then move past.

2. Min-heap of size k

Count with a Map. Maintain a min-heap of (count, num) of size k; on each new entry, push then pop if size > k. Heap top is the smallest of the top-k.

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

function topKFrequentHeap(nums, k) {
  const count = new Map();
  for (const n of nums) count.set(n, (count.get(n) || 0) + 1);
  const heap = new MinHeap();
  for (const [num, c] of count) {
    heap.push([c, num]);
    if (heap.size() > k) heap.pop();
  }
  const out = [];
  while (heap.size()) out.push(heap.pop()[1]);
  return out;
}

Tradeoff: O(n log k) — strictly better than O(n log n) when k << n. Constant memory beyond the counts. Good when k is bounded; less attractive when k is close to n.

3. Bucket sort (optimal O(n))

Counts can be at most n, so create n+1 buckets indexed by frequency. Walk from highest bucket down, collecting elements until you have k.

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

Tradeoff: True O(n). Wins decisively when k can be close to n or when the heap setup cost matters. The textbook answer for the 'better than O(n log n)' constraint. Shopify interviewers love when candidates jump to bucket sort directly.

Shopify-specific tips

Shopify's grading bar: name both heap and bucket sort, then justify your choice. If you write only the heap version, expect 'can you do better than O(n log k)?' as the immediate follow-up. The streaming variant ('what if nums is a stream?') is the second-most-common follow-up — answer: heap of size k with online updates.

Common mistakes

  • Sorting and taking the top k — works but violates the explicit constraint.
  • Using a max-heap of size n instead of a min-heap of size k — that's O(n log n), not O(n log k).
  • Off-by-one in the bucket array size — buckets need indices 0..n, not 0..n-1.
  • Forgetting that multiple elements can share a frequency (must iterate within each bucket).

Follow-up questions

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

  • Streaming version — Top K from an infinite stream (Misra-Gries or Count-Min Sketch + heap).
  • Top K Frequent Words (LeetCode 692) — lexicographic tiebreak.
  • Top K elements by custom comparator (e.g., recency-weighted frequency).
  • Distributed Top K across multiple machines.
  • What if k > number of unique elements? (Return all; ask the interviewer to clarify.)

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 choose heap over bucket sort?

When memory is tight (heap is O(k), bucket sort is O(n)) or when you don't know n upfront (streaming). Bucket sort needs to materialize n+1 buckets, which is wasteful when n is huge but the answer is small.

Is bucket sort actually faster in practice?

For small k yes, especially when n is small enough that the heap's constant factor (array operations, comparisons) costs more than the bucket overhead. For very large k near n, the heap is comparable. The asymptotic win is real but the practical win is modest.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →