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


  • 0
    D

    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.
        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
    

Log in to reply
 

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