Top K Frequent Elements#

Given an array of integers and a number k, return the k values that appear most often. The answer may be returned in any order, and the value of k is always valid for the input.

Example#

Input: nums = [1, 1, 1, 2, 2, 3], k = 2 Output: [1, 2] because 1 appears three times and 2 appears twice.

Brute force#

Count the frequency of every value, then sort all values by frequency and take the first k. Sorting the whole set of distinct values is the bottleneck.

• Time: O(n log n) for the sort.
• Space: O(n) for the counts.

Optimal approach#

Count frequencies with a hash map, then place each value into a bucket indexed by its frequency. Because no frequency can exceed the array length, there are at most n + 1 buckets. Walk the buckets from highest frequency down and collect values until you have k of them. This bucket sort avoids a comparison sort and runs in linear time.

Python solution#

 1from collections import Counter
 2
 3
 4def top_k_frequent(nums, k):
 5    counts = Counter(nums)
 6    buckets = [[] for _ in range(len(nums) + 1)]
 7    for value, freq in counts.items():
 8        buckets[freq].append(value)
 9
10    result = []
11    for freq in range(len(buckets) - 1, 0, -1):
12        for value in buckets[freq]:
13            result.append(value)
14            if len(result) == k:
15                return result
16    return result

Complexity#

• Time: O(n), counting and bucket collection are both linear.
• Space: O(n) for the counts and buckets.

This problem combines the hashing pattern with bucket sorting to beat a comparison sort. Keep drilling with the 60-day challenge.