Top K Frequent Elements

Problem statement

From an integer list, return any k values that show up most often.

Example:

Input:

numbers = [1, 2, 3, 4, 5, 6, 1, 2, 1, 2], k = 2

Expected output:

[1, 2]

Why: 1 and 2 appear more than anything else.

Practice on LeetCode: Top K Frequent Elements

Approach 1: Hash map + sort

Count frequencies in a hash map, collect the unique keys, and sort them by frequency descending. Return the first k keys.

Time: O(n + m log m) where m is the number of unique values (m ≤ n).
Space: O(m).

package main

import "sort"

func topKFrequent(nums []int, k int) []int {
	hashMap := make(map[int]int)
	for i := 0; i < len(nums); i++ {
		hashMap[nums[i]]++
	}

	arr := make([]int, 0, len(hashMap))
	for key := range hashMap {
		arr = append(arr, key)
	}

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

	return arr[:k]
}

Approach 2: Hash map + min-heap

Count frequencies, then keep a min-heap of size k ordered by count. Every time the heap grows past k, pop the smallest frequency. What remains are the top k frequent values.

Time: O(n + m log k) — better than full sort when k is much smaller than m.
Space: O(m + k).

package main

import "container/heap"

// item represents a (value, frequency) pair
type item struct {
	val   int
	count int
}

// minHeap implements heap.Interface, ordered by count ascending
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
	n := len(old)
	popped := old[n-1]
	*h = old[:n-1]
	return popped
}

func topKFrequent(nums []int, k int) []int {
	// Step 1: count frequencies
	freq := make(map[int]int)
	for _, n := range nums {
		freq[n]++
	}

	// Step 2: maintain a min-heap of size k
	h := &minHeap{}
	heap.Init(h)

	for val, count := range freq {
		heap.Push(h, item{val: val, count: count})
		if h.Len() > k {
			heap.Pop(h) // remove smallest-frequency element
		}
	}

	// Step 3: extract results from the heap
	result := make([]int, h.Len())
	for i := len(result) - 1; i >= 0; i-- {
		result[i] = heap.Pop(h).(item).val
	}

	return result
}

Which approach to use?

Prefer hash map + sort when you want the simplest correct solution and m is small.
Prefer hash map + min-heap when k << m and you care about the log k bound — a classic heap / priority-queue interview follow-up.