# Ruby Union Find exceeding time limit, help?

• ``````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
``````

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