Top K Frequent Elements

LeetCode 347 · View on LeetCode

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

Solution 1: Bucket Sort — O(n)

Use frequency as an index. Since no element appears more than n times, create buckets of size n+1 and walk from highest frequency down.

package main

import "fmt"

func topKFrequent(nums []int, k int) []int {
	freq := map[int]int{}
	for _, n := range nums {
		freq[n]++
	}

	// buckets[i] holds numbers that appear exactly i times
	buckets := make([][]int, len(nums)+1)
	for num, count := range freq {
		buckets[count] = append(buckets[count], num)
	}

	result := []int{}
	for i := len(buckets) - 1; i >= 0 && len(result) < k; i-- {
		result = append(result, buckets[i]...)
	}
	return result
}

func main() {
	fmt.Println(topKFrequent([]int{1, 1, 1, 2, 2, 3}, 2)) // [1 2]
	fmt.Println(topKFrequent([]int{1}, 1))                  // [1]
}

Time: O(n) — one pass to count, one pass to bucket, one pass to collect. Space: O(n) — frequency map + buckets.

Solution 2: Min-Heap — O(n log k)

Maintain a min-heap of size k. For each unique element, push it onto the heap. If the heap exceeds size k, pop the least frequent — this ensures only the top k remain.

package main

import (
	"container/heap"
	"fmt"
)

type Item struct{ num, count int }
type MinHeap []Item

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool   { return h[i].count < h[j].count }
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.(Item)) }
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 {
	freq := map[int]int{}
	for _, n := range nums {
		freq[n]++
	}

	h := &MinHeap{}
	for num, count := range freq {
		heap.Push(h, Item{num, count})
		if h.Len() > k {
			heap.Pop(h)
		}
	}

	result := make([]int, h.Len())
	for i := len(result) - 1; i >= 0; i-- {
		result[i] = heap.Pop(h).(Item).num
	}
	return result
}

func main() {
	fmt.Println(topKFrequent([]int{1, 1, 1, 2, 2, 3}, 2)) // [1 2]
	fmt.Println(topKFrequent([]int{1}, 1))                  // [1]
}

Time: O(n log k) — each push/pop is O(log k), done for each unique element. Space: O(n) — frequency map + heap of size k.

Solution 3: Sort by Frequency — O(n log n)

The simplest approach: collect unique elements, sort them by frequency descending, take the first k.

package main

import (
	"fmt"
	"sort"
)

func topKFrequent(nums []int, k int) []int {
	freq := map[int]int{}
	for _, n := range nums {
		freq[n]++
	}

	unique := make([]int, 0, len(freq))
	for num := range freq {
		unique = append(unique, num)
	}

	sort.Slice(unique, func(i, j int) bool {
		return freq[unique[i]] > freq[unique[j]]
	})

	return unique[:k]
}

func main() {
	fmt.Println(topKFrequent([]int{1, 1, 1, 2, 2, 3}, 2)) // [1 2]
	fmt.Println(topKFrequent([]int{1}, 1))                  // [1]
}

Time: O(n log n) — dominated by the sort. Space: O(n) — frequency map + unique slice.

Comparison

Approach	Time	Space	Notes
Bucket sort	O(n)	O(n)	Optimal. Uses frequency as array index
Min-heap	O(n log k)	O(n)	Good when k is small. Streaming-friendly
Sort	O(n log n)	O(n)	Simplest code. Fine for small inputs