Ruby Union Find exceeding time limit, help?


  • 0
    T
    def num_islands2(m, n, positions)
        @m = m
        @n = n
        @grid = {}
        @roots = {}
        @num_islands = []
        positions.each do |p|
          nodes = neighbors(p[0],p[1]).map {|n| @grid[n.to_s]}.compact
          parents = nodes.map { |n| n.root }.uniq
          @grid[p.to_s] = Node.new(p[0],p[1])
          join_nodes(parents, @grid[p.to_s])
          @num_islands << @roots.count
          puts @roots.count
        end
        @num_islands
    end
    
    def join_nodes(nodes, new_node)
      @roots[new_node] = new_node.pos and return if nodes.length == 0
      if nodes.length > 1
        nodes.each do |n|
          n.parent = new_node
          @roots.delete n
        end
        @roots[new_node] = new_node.pos
      else
        new_node.parent = nodes.first
      end
    end
    
    def neighbors(i,j)
      [[i-1,j],[i,j-1],[i+1,j],[i,j+1]].select {|p| valid?(p)}
    end
    
    def valid?(pos)
      pos[0] >= 0 && pos[0] < @m && pos[1] >= 0 && pos[1] < @n
    end
    
    class Node
      attr_accessor :parent, :x, :y
    
      def initialize(x, y)
        @x, @y = x, y
      end
    
      def pos
        [@x,@y]
      end
    
      def root
        nodes = []
        node = self
        while !node.parent.nil?
          nodes << node
          node = node.parent
        end
        nodes.each {|n| n.parent = node} if nodes.count > 1
        node
      end
    end
    

Log in to reply
 

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