There are three steps:

- Count the frequency of all of the elements ( O(n) )
- Create buckets for the count values, store the count-keys into each bucket so items with the same count are bunched together ( O(n) ). Store the maximum.
- From the maximum down to 1, find a bucket with the current frequency, and take as many elements from that bucket as necessary. ( O(n) since we aren't iterating over the bucket, instead just greedily grabbing items [0..remaining] using the range feature.

```
def top_k_frequent(nums, k)
counts = item_counts(nums)
max_freq, frequency_buckets = value_buckets_and_max(counts)
top_k_freq = []
max_freq.downto(1) do |freq|
next unless frequency_buckets[freq]
top_k_freq += frequency_buckets[freq][0..k-top_k_freq.count] #O(n), we avoid iterating over each bucket's list by just grabbing as much as necessary from each bucket.
return top_k_freq if top_k_freq.count == k
end
end
def value_buckets_and_max(counts) #O(N)
max_freq = -Float::INFINITY
frequency_buckets = {}
counts.each do |count|
max_freq = count.last if count.last > max_freq
if frequency_buckets[count.last]
frequency_buckets[count.last] << count.first
else
frequency_buckets[count.last] = [count.first]
end
end
[max_freq, frequency_buckets]
end
def item_counts(nums) #O(N)
counts = {}
nums.each do |num|
if counts[num]
counts[num] += 1
else
counts[num] = 1
end
end
counts
end
```