# Two solutions with Bucket Sort O(N) and Priority Queue O(NlogK)

• I believe this problem is waiting a Priority Queue solution, as it says

Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

So I implement a minimum heap first, with time complexity O(NlogK).

``````  # O(NlogK) using minimum priority queue
def top_k_frequent(nums, k)
counter = nums.reduce( Hash.new(0) ) do |ha, num|
ha[num] += 1
ha
end

pg = PriorityQueue.new
pair = Struct.new(:key, :value)

counter.each do |num, count|
node = pair.new(count, num)

if pg.size < k
pg.insert node
else
next if node.key <= pg.get_min.key

pg.delete_min
pg.insert node
end
end

# puts "pg: #{pg.array} size: #{pg.size}"

# generate results
results = []
while pg.size > 0
results.unshift pg.delete_min
end

# puts "results: #{results}"

results.map(&:value)
end

# A minimum priority queue
class PriorityQueue
attr_accessor :array, :size

def initialize
@array = [nil]
@size = 0
end

def insert(node)
self.size += 1
array[size] = node
swim(size)
end

def delete_min
res = get_min

swap(1, size)
self.size -= 1
sink(1)

res
end

def get_min
array[1]
end

private

def swim(k)
while k/2 >= 1
j = k/2

break if !less(k, j)

swap(j, k)
k = j
end
end

def sink(k)
while 2*k <= size
j = 2*k
j += 1 if j+1 <= size && less(j+1, j)

break if !less(j, k)

swap(j, k)
k = j
end
end

def less(j, k)
array[j].key < array[k].key
end

def swap(j, k)
t = array[j]; array[j] = array[k]; array[k] = t
end

end

``````

Then I noticed that Bucket Sort can also solve the problem, within linear time. Good!

``````  # O(N) using bucket sort
def top_k_frequent(nums, k)
counter = nums.reduce( Hash.new(0) ) do |ha, num|
ha[num] += 1
ha
end

# puts "counter: #{counter}"

max_count = 0
frequency = counter.reduce( Hash.new{|hh,kk| hh[kk] = Array.new } ) do |ha, (num, count)|
max_count = count if max_count < count
ha[count] << num
ha
end

# puts "frequency: #{frequency}"

results = []
max_count.downto(1) do |count|
break if results.count == k

while !frequency[count].empty? && results.count < k
results << frequency[count].shift
end
end

results
end
``````

P.S. Quick Select could also work, estimated time complexityO(KN)

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