Skip to main content

347. Top K Frequent Elements

mediumAsked at Atlassian

Top K Frequent Elements is Atlassian's heap-and-counting interview classic. Given an integer array and an integer k, return the k most frequent elements. Atlassian asks it because top-k ranking is the algorithmic backbone behind Confluence's 'most active pages' and Jira's 'top reporters' surfaces.

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

Source citations

Public interview reports confirming this problem appears in Atlassian loops.

  • Glassdoor (2026-Q1)— Atlassian SWE-II onsite reports cite Top K Frequent Elements after K Closest Points as the second heap problem.
  • Blind (2025-10)— Atlassian interview threads recurring mention of Top K Frequent as the 'ranking systems' question.

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. Sort by frequency (violates time constraint)

Count with a map, sort entries by frequency descending, take first k.

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

Tradeoff: Idiomatic but EXPLICITLY rejected by the LeetCode problem statement which mandates better than O(n log n). Useful only as the 'and here's the obvious bad answer' framing — never as your final solution.

2. Min-heap of size k

Count frequencies. Maintain a min-heap of (count, num) of size k; for each entry, push then pop-min if size > k.

Time
O(n log k)
Space
O(n + k)
class MinHeap {
  constructor() { this.h = []; }
  size() { return this.h.length; }
  peek() { return this.h[0]; }
  push(v) {
    this.h.push(v);
    let i = this.h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.h[p][0] <= this.h[i][0]) break;
      [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
      i = p;
    }
  }
  pop() {
    const top = this.h[0];
    const last = this.h.pop();
    if (this.h.length) {
      this.h[0] = last;
      let i = 0;
      for (;;) {
        const l = 2 * i + 1;
        const r = 2 * i + 2;
        let m = i;
        if (l < this.h.length && this.h[l][0] < this.h[m][0]) m = l;
        if (r < this.h.length && this.h[r][0] < this.h[m][0]) m = r;
        if (m === i) break;
        [this.h[i], this.h[m]] = [this.h[m], this.h[i]];
        i = m;
      }
    }
    return top;
  }
}
function topKFrequentHeap(nums, k) {
  const counts = new Map();
  for (const n of nums) counts.set(n, (counts.get(n) || 0) + 1);
  const heap = new MinHeap();
  for (const [num, c] of counts) {
    heap.push([c, num]);
    if (heap.size() > k) heap.pop();
  }
  return heap.h.map(([, n]) => n);
}

Tradeoff: Meets the n log k requirement. Atlassian-accepted answer at SWE-II. Heap hand-written by you (no built-in priority queue in JS); spend the 5 minutes.

3. Bucket sort (optimal O(n))

Count frequencies; create buckets[freq] = list of nums with that freq. Walk buckets from high freq to low, collect first k.

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

Tradeoff: True O(n) — the optimal Atlassian wants at Senior+. Insight: frequencies are bounded by n, so an array of size n+1 buckets is enough. Allocates more memory than the heap but no log factor. Lead with this version at Senior+; mention heap as 'also valid'.

Atlassian-specific tips

Atlassian explicitly tests whether you notice the LeetCode constraint 'better than O(n log n)' — leading with the sort version and stopping costs the question even if it returns the right answer. The 'aha' is realizing frequencies are bounded by the array length, so bucket sort wins. Mention both heap (canonical) and bucket sort (optimal) and let the interviewer choose; many Atlassian Senior interviewers explicitly grade 'recognized the bucket sort opportunity'.

Common mistakes

  • Reading the LeetCode constraint sloppily and shipping the n log n sort version.
  • On the heap version, using a max-heap of size n — that's n log n which doesn't meet the constraint.
  • On bucket sort, forgetting to allocate buckets of size n+1 (not n) — counts can equal n itself.

Follow-up questions

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

  • Top K Frequent Words (LeetCode 692) — strings with lexicographic tie-breaker; same heap pattern but the comparator matters.
  • Streaming top-k — elements arrive one at a time; how would you maintain a live top-k? (heap is wrong; use count-min sketch + heap.)
  • What if the array were too large to fit in memory? Map-reduce style: count locally, merge with a min-heap globally.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Heap or bucket sort at Atlassian?

At SWE-II both pass with full marks. At Senior+ the bucket sort is what they're looking for because it hits the true O(n). Lead with bucket sort if the interviewer is at Senior+ ('staff signal'); lead with heap if it's a SWE-II loop and you want to communicate progression.

Why is bucket sort O(n)?

Counting is O(n), bucket fill is O(unique_count) which is <= n, and the bucket walk visits at most n items total (sum of bucket sizes = number of unique elements). All three steps are linear.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →