# O(n) Ruby solution (3 loops) (with explanation)

• There are three steps:

1. Count the frequency of all of the elements ( O(n) )
2. 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.
3. 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.
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
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.