Python UnionFind solution


  • 0
    N
    class UnionFind:
    
    def __init__(self, size):
        self.parent = [i for i in xrange(size)]
        self.grid = [0] * size
        self.count = 0
    
    def add(self, x):
        self.count += 1
        self.grid[x] = 1
    
    def find(self, x):
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x
    
    def union(self, x, y):
        parent_x = self.find(x)
        parent_y = self.find(y)
        if parent_x != parent_y:
            self.count -= 1
            self.parent[parent_x] = parent_y 
    
    class Solution:
    
    def numIslands2(self, m, n, positions):
    
        if m <= 0 or n <= 0:
            return 0
        
        size = m * n
        union_find = UnionFind(size=size)
        result = []
        for x, y in map(tuple, positions):
            p_one = x * n + y
            if not union_find.grid[p_one]:
                union_find.add(p_one)
            for i, j in [(x - 1, y), (x + 1, y), (x, y + 1), (x, y - 1)]:
                p_two = i * n + j
                if 0 <= i < m and 0 <= j < n and union_find.grid[p_two]:
                    union_find.union(p_one, p_two)
            result.append(union_find.count)
        return result

Log in to reply
 

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