Kahn's algorithm with tweaked data structure - 65ms in Ruby


  • 0
    D

    I tried several algorithms from DFS, Tarjan, Kahn, and this is the fastest one based on Kahn with some modifications on data structure to make use of hashmap.

    Ruby is slow, but the submission ran in 65ms and beat 100% ruby submissions.

    # @param {Integer} num_courses
    # @param {Integer[][]} prerequisites
    # @return {Boolean}
    def can_finish(num_courses, prerequisites)
        incoming = Hash.new(0)
        neighbors = {}
        
        prerequisites.each do |to, from|
            incoming[from] += 1
            (neighbors[to] ||= []) << from
        end
        
        queue = []
        num_courses.times do |i|
            queue << i if incoming[i] == 0
        end
        
        while queue.size > 0 do
            v = queue.shift
            next unless neighbors[v]
            
            neighbors[v].each do |n|
                incoming[n] -= 1
                queue << n if incoming[n] == 0
            end
            neighbors[v] = nil
        end
        
        neighbors.values.compact.empty?
    end
    

Log in to reply
 

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