347. Top K Frequent Elements (Medium)

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 problem guarantees the answer is unique.

Example

nums = [1,1,1,2,2,3], k = 2 → [1, 2]
nums = [1], k = 1 → [1]

Follow-up: can you do better than $O(n log n)$ ?

LeetCode 347 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, count, then sort

Count frequencies with a hash map, then sort by count descending, take the first k.

from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    counts = Counter(nums)                          # L1: O(n) build counter
    return [num for num, _ in counts.most_common(k)]  # L2: O(n log k) heap internally

function topKFrequent(nums: number[], k: number): number[] {
    const counts = new Map<number, number>();        // L1: O(n) build counter
    for (const x of nums) counts.set(x, (counts.get(x) ?? 0) + 1);
    return [...counts.entries()]
        .sort((a, b) => b[1] - a[1])               // L2: O(n log n) sort
        .slice(0, k)
        .map(([num]) => num);
}

import "sort"

func topKFrequent(nums []int, k int) []int {
  counts := make(map[int]int)                      // L1: O(n) build counter
  for _, n := range nums { counts[n]++ }
  type pair struct{ num, cnt int }
  entries := make([]pair, 0, len(counts))
  for num, cnt := range counts { entries = append(entries, pair{num, cnt}) }
  sort.Slice(entries, func(i, j int) bool { return entries[i].cnt > entries[j].cnt }) // L2: O(n log n)
  result := make([]int, k)
  for i := 0; i < k; i++ { result[i] = entries[i].num }
  return result
}

Where the time goes, line by line

Variables: n = len(nums), k = number of top elements requested.

Line	Per-call cost	Times executed	Contribution
L1 (Counter)	$O(n)$	1	$O(n)$
L2 (most_common)	$O(n log k)$	1	$O(n log k)$ ← dominates

most_common(k) uses a heap internally ( $O(n log k)$ ), not a full sort.

Complexity

Time: $O(n log n)$ . Sorting all distinct elements.
Space: $O(n)$ for the counter.

most_common(k) internally uses a heap ( $O(n log k)$ ), but for “brute” purposes treat it as a full sort.

Swift

final class Solution {
    func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
        var counts: [Int: Int] = [:]; for value in nums { counts[value, default: 0] += 1 }
        return counts.sorted { $0.value == $1.value ? $0.key < $1.key : $0.value > $1.value }.prefix(k).map(\.key)
    }
}

Approach 2: Size-k min-heap

Maintain a heap of size k over (count, value) pairs. Evict the smallest whenever the heap grows past k.

from collections import Counter
import heapq

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    counts = Counter(nums)                 # L1: O(n) build counter
    heap = []                              # L2: O(1)
    for num, cnt in counts.items():        # L3: loop over d distinct elements
        heapq.heappush(heap, (cnt, num))   # L4: O(log k) per push
        if len(heap) > k:                  # L5: O(1) check
            heapq.heappop(heap)            # L6: O(log k) pop
    return [num for _, num in heap]        # L7: O(k)

function topKFrequent(nums: number[], k: number): number[] {
    const counts = new Map<number, number>();         // L1: O(n) build counter
    for (const x of nums) counts.set(x, (counts.get(x) ?? 0) + 1);
    // Sort entries by count ascending, keep last k
    const entries = [...counts.entries()].sort((a, b) => a[1] - b[1]); // L3-L4: O(d log d)
    return entries.slice(-k).map(([num]) => num);    // L7: O(k)
}

import (
  "container/heap"
)

type pair struct{ cnt, num int }
type minHeap []pair

func (h minHeap) Len() int            { return len(h) }
func (h minHeap) Less(i, j int) bool  { return h[i].cnt < h[j].cnt }
func (h minHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h = append(*h, x.(pair)) }
func (h *minHeap) Pop() interface{}   { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }

func topKFrequent(nums []int, k int) []int {
  counts := make(map[int]int)                       // L1: O(n) build counter
  for _, n := range nums { counts[n]++ }
  h := &minHeap{}
  heap.Init(h)
  for num, cnt := range counts {                    // L3: loop over d distinct elements
    heap.Push(h, pair{cnt, num})                  // L4: O(log k) per push
    if h.Len() > k { heap.Pop(h) }               // L5-L6: O(log k) pop
  }
  result := make([]int, h.Len())
  for i := range result { result[i] = (*h)[i].num } // L7: O(k)
  return result
}

Where the time goes, line by line

Variables: n = len(nums), k = number of top elements requested, d = number of distinct elements (d ≤ n).

Line	Per-call cost	Times executed	Contribution
L1 (Counter)	$O(n)$	1	$O(n)$
L3 (loop)	$O(1)$	d	$O(d)$
L4 (heappush)	$O(log k)$	d	$O(d log k)$ ← dominates
L6 (heappop)	$O(log k)$	at most d-k	$O(d log k)$
L7 (extract)	$O(k)$	1	$O(k)$

Since d ≤ n, the total is $O(n log k)$ .

Complexity

Time: $O(n log k)$ , driven by L4/L6 (heap push/pop on a size-k heap). Each of up to n distinct elements pushed/popped on a size-k heap.
Space: $O(n + k)$ . Counter + heap.

When k is small relative to n, this is noticeably faster than the $O(n log n)$ sort.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
        var counts: [Int: Int] = [:]; for value in nums { counts[value, default: 0] += 1 }
        var heap = BinaryHeap<(Int, Int)> { a, b in a.0 == b.0 ? a.1 > b.1 : a.0 < b.0 }
        for (value, count) in counts { heap.insert((count, value)); if heap.count > k { _ = heap.removeRoot() } }
        var result: [(Int, Int)] = []; while let item = heap.removeRoot() { result.append(item) }
        return result.sorted { $0.0 == $1.0 ? $0.1 < $1.1 : $0.0 > $1.0 }.map(\.1)
    }
}

Approach 3: Bucket sort by frequency (optimal)

Frequencies are bounded by n (no value can appear more than n times). Bucket each distinct element into buckets[freq], then scan from high to low.

from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    counts = Counter(nums)                         # L1: O(n) build counter
    buckets = [[] for _ in range(len(nums) + 1)]   # L2: O(n) n+1 buckets
    for num, cnt in counts.items():                # L3: loop d distinct elements
        buckets[cnt].append(num)                   # L4: O(1) append

    result = []
    for cnt in range(len(buckets) - 1, 0, -1):    # L5: scan buckets high-to-low
        for num in buckets[cnt]:                   # L6: visit elements in bucket
            result.append(num)                     # L7: O(1) append
            if len(result) == k:                   # L8: O(1) check
                return result                      # L9: O(1) early return
    return result

function topKFrequent(nums: number[], k: number): number[] {
    const counts = new Map<number, number>();         // L1: O(n) build counter
    for (const x of nums) counts.set(x, (counts.get(x) ?? 0) + 1);
    const buckets: number[][] = Array.from({length: nums.length + 1}, () => []); // L2: O(n)
    for (const [num, cnt] of counts) buckets[cnt].push(num); // L3-L4: O(d)

    const result: number[] = [];
    for (let cnt = buckets.length - 1; cnt > 0; cnt--) { // L5: scan high-to-low
        for (const num of buckets[cnt]) {               // L6: visit elements
            result.push(num);                           // L7: O(1)
            if (result.length === k) return result;     // L8-L9: early return
        }
    }
    return result;
}

func topKFrequent(nums []int, k int) []int {
  counts := make(map[int]int)                        // L1: O(n) build counter
  for _, n := range nums { counts[n]++ }
  buckets := make([][]int, len(nums)+1)              // L2: O(n) n+1 buckets
  for num, cnt := range counts {
    buckets[cnt] = append(buckets[cnt], num)       // L3-L4: O(1) append
  }
  result := []int{}
  for cnt := len(buckets) - 1; cnt > 0; cnt-- {     // L5: scan high-to-low
    for _, num := range buckets[cnt] {             // L6: visit elements
      result = append(result, num)               // L7: O(1)
      if len(result) == k { return result }      // L8-L9: early return
    }
  }
  return result
}

Where the time goes, line by line

Variables: n = len(nums), k = number of top elements requested.

Line	Per-call cost	Times executed	Contribution
L1 (Counter)	$O(n)$	1	$O(n)$
L2 (init buckets)	$O(n)$	1	$O(n)$
L3, L4 (bucketing)	$O(1)$	d ≤ n	$O(n)$
L5-L9 (scan + collect)	$O(1)$ per element	at most n	$O(n)$ ← dominates total

Every distinct element is bucketed once and visited at most once during the scan. The bucket array has n+1 slots, all accessed in $O(1)$ .

Complexity

Time: $O(n)$ , driven by L1/L2 (linear setup) plus the $O(n)$ total scan in L5-L9. Counter is $O(n)$ ; bucketing is $O(n)$ ; the scan visits at most n elements.
Space: $O(n)$ for counter and buckets.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
        var counts: [Int: Int] = [:]; for value in nums { counts[value, default: 0] += 1 }; var buckets = Array(repeating: [Int](), count: nums.count + 1)
        for (value, count) in counts { buckets[count].append(value) }
        var result: [Int] = []; for count in stride(from: buckets.count - 1, through: 1, by: -1) { for value in buckets[count].sorted() { result.append(value); if result.count == k { return result } } }
        return result
    }
}

Summary

Approach	Time	Space
Sort by count	$O(n log n)$	$O(n)$
Size-k min-heap	$O(n log k)$	$O(n + k)$
Bucket sort	$O(n)$	$O(n)$

Bucket sort beats the heap when k is not trivially small; the heap wins on streaming input or when you need online updates. Choose based on the scenario.

# Quick smoke tests, paste into a REPL or save as test_top_k_frequent.py and run.
# Uses the canonical implementation (Approach 3: bucket sort).

from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    counts = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, cnt in counts.items():
        buckets[cnt].append(num)
    result = []
    for cnt in range(len(buckets) - 1, 0, -1):
        for num in buckets[cnt]:
            result.append(num)
            if len(result) == k:
                return result
    return result

def _run_tests():
    assert sorted(top_k_frequent([1,1,1,2,2,3], 2)) == [1, 2]
    assert top_k_frequent([1], 1) == [1]
    assert sorted(top_k_frequent([1,2], 2)) == [1, 2]
    # All same frequency, k=1: any one element is valid
    r = top_k_frequent([1,2,3], 1)
    assert len(r) == 1 and r[0] in [1, 2, 3]
    print("all tests pass")

function assert(condition: boolean, msg: string = ''): void {
    if (!condition) throw new Error(msg || 'Assertion failed');
}

function topKFrequent(nums: number[], k: number): number[] {
    const counts = new Map<number, number>();
    for (const x of nums) counts.set(x, (counts.get(x) ?? 0) + 1);
    const buckets: number[][] = Array.from({length: nums.length + 1}, () => []);
    for (const [num, cnt] of counts) buckets[cnt].push(num);
    const result: number[] = [];
    for (let cnt = buckets.length - 1; cnt > 0; cnt--) {
        for (const num of buckets[cnt]) {
            result.push(num);
            if (result.length === k) return result;
        }
    }
    return result;
}

assert(JSON.stringify([...topKFrequent([1,1,1,2,2,3], 2)].sort()) === JSON.stringify([1,2]));
assert(JSON.stringify(topKFrequent([1], 1)) === JSON.stringify([1]));
assert(JSON.stringify([...topKFrequent([1,2], 2)].sort()) === JSON.stringify([1,2]));
const r = topKFrequent([1,2,3], 1);
assert(r.length === 1 && [1,2,3].includes(r[0]));
console.log("all tests pass");

Arrays, input and bucket representation
Hash Tables, frequency counting (Counter)
Heaps / Priority Queues, size-k min-heap pattern

Hash Map Counting, frequency-table tactics for turning membership, complement, and multiplicity questions into direct lookups.
Top K, selection tactics for finding the largest, smallest, or most frequent K items without fully ordering everything.

347. Top K Frequent Elements (Medium)

Problem

Try it yourself

Approach 1: Brute force, count, then sort

Approach 2: Size-k min-heap

Approach 3: Bucket sort by frequency (optimal)

Summary

Test cases

Related data structures

Related concepts