Top K Frequent Elements

Medium

The problem

Given a list of numbers and a number k, return the k numbers that appear most often. You may return them in any order.

Example 1
Input: nums = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]
1 appears 3 times and 2 appears 2 times; 3 appears only once.
Example 2
Input: nums = [7], k = 1
Output: [7]
There is only one number to choose.

Limits

1 ≤ nums.length ≤ 100,000
1 ≤ k ≤ the number of different values in nums
The answer is unique: there is no tie for the last place

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

First count, then think about how to pick the biggest counts without a full sort.

The idea

Count with a map, then bucket numbers by frequency (index = count) and read buckets from the highest frequency down until you have k.

Target: O(n) time, O(n) space

Go function shape

func topKFrequent(nums []int, k int) []int

Reference solution

Tested with go test. Try it yourself first, then compare.

// TopKFrequent: count first, then pick the k most frequent values.
func TopKFrequent(nums []int, k int) []int {
	freq := map[int]int{}
	for _, v := range nums {
		freq[v]++
	}
	keys := make([]int, 0, len(freq))
	for v := range freq {
		keys = append(keys, v)
	}
	sort.Slice(keys, func(a, b int) bool {
		if freq[keys[a]] != freq[keys[b]] {
			return freq[keys[a]] > freq[keys[b]]
		}
		return keys[a] < keys[b]
	})
	if k > len(keys) {
		k = len(keys)
	}
	return keys[:k]
}

Read the lesson: Arrays & Hash Map