Compact Python.


  • 7

    Pretty much just Wikipedia's Disjoint-set forests, using "union by rank" and "path compression". I don't see the point of m and n, so I ignore them.

    def numIslands2(self, m, n, positions):
        parent, rank, count = {}, {}, [0]
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        def union(x, y):
            x, y = find(x), find(y)
            if x != y:
                if rank[x] < rank[y]:
                    x, y = y, x
                parent[y] = x
                rank[x] += rank[x] == rank[y]
                count[0] -= 1
        def add((i, j)):
            x = parent[x] = i, j
            rank[x] = 0
            count[0] += 1
            for y in (i+1, j), (i-1, j), (i, j+1), (i, j-1):
                if y in parent:
                    union(x, y)
            return count[0]
        return map(add, positions)
    

    Too bad Python 2 doesn't have nonlocal yet, hence the somewhat ugly count[0] "hack". Here's a different way:

    def numIslands2(self, m, n, positions):
        parent, rank = {}, {}
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        def union(x, y):
            x, y = find(x), find(y)
            if x == y:
                return 0
            if rank[x] < rank[y]:
                x, y = y, x
            parent[y] = x
            rank[x] += rank[x] == rank[y]
            return 1
        counts, count = [], 0
        for i, j in positions:
            x = parent[x] = i, j
            rank[x] = 0
            count += 1
            for y in (i+1, j), (i-1, j), (i, j+1), (i, j-1):
                if y in parent:
                    count -= union(x, y)
            counts.append(count)
        return counts

  • 1
    K

    Hi, I tried your first method, without rank, it still AC. I wonder why you have rank here. As far as I know from the wiki, it seems to make it fast. Am I right?

    def numIslands2(self, m, n, positions):
        parent, rank, count = {}, {}, [0]
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
            
        def union(x, y):
            x, y = find(x), find(y)
            if x != y:
                # if rank[x] < rank[y]:
                #     x, y = y, x
                parent[y] = x
                count[0] -= 1
        def add((i, j)):
            x = parent[x] = i, j
            rank[x] = 0
            count[0] += 1
            for y in (i+1, j), (i-1, j), (i, j+1), (i, j-1):
                if y in parent:
                    union(x, y)
            return count[0]
        return map(add, positions)
    

  • 0

    Yes, it's for speed.


  • 2

    @StefanPochmann Very similar to yours, perhaps a bit more Object-Oriented. BTW, what is your runtime?

    
    class UnionFind(object):
        
        def __init__(self, n):
            self.idxs = [-1] * n
            self.rank = [0] * n
            self.unions = 0
        
        def find(self, x):
            if x == self.idxs[x]: return x
            self.idxs[x] = self.find(self.idxs[x])
            return self.idxs[x]
        
        def union(self, x, y):
            rx = self.find(x)
            ry = self.find(y)
            if rx != ry:
                if self.rank[rx] > self.rank[ry]:
                    self.idxs[ry] = rx
                else:
                    self.idxs[rx] = ry
                    if self.rank[ry] == self.rank[rx]:
                        self.rank[ry] += 1
                self.unions +=1
        
    
    class Solution(object):
        def numIslands2(self, m, n, positions):
            grid, UF, res = [[[0] * n] * m], UnionFind(m * n), []
            for i, (r, c) in enumerate(positions):
                UF.idxs[n * r + c] = n * r + c
                for d in {(-1,0), (1,0), (0,1), (0,-1)}:
                    px, py = r + d[0], c + d[1]
                    if 0 <= px < m and 0 <= py < n and UF.idxs[n * px + py] != -1:
                        UF.union(n * px + py, n * r + c)
                res.append(i + 1 - UF.unions)
            return res
        # Runtime: 504ms
    

  • 2
    L

    Thanks for sharing the solution! But I have a simple maybe stupid question.
    Why do you use count = [0]? I try to just use count = 0, but there is this error with 'no defined variable', count. This is my code

    def numIslands2(self, m, n, positions):
        """
        :type m: int
        :type n: int
        :type positions: List[List[int]]
        :rtype: List[int]
        """
        parent = {}
        count = 0
        result = []
        def find(x):
            if parent[x] != x:
                return find(parent[x])
            else:
                return x
        
        def union(x, y):
            x, y = find(x), find(y)
            if x!=y:
                parent[y] = x
                count -= 1
                
        for pos in positions:
            i, j = pos
            pos = (i, j)
            parent[pos] = pos
            count += 1
            for neighbor in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                if neighbor in parent:
                    union(pos, neighbor)
            result.append(count)
        return result
    

    Thanks in advance!


  • 0
    X

    What if we allow removals in this problem??


  • 0
    J

    @XuhuiWang
    I've thought for that problem for several time, and what I can think of is the pretty naive algorithm, when we remove certain island and make it into water, perform dfs on 4 directions.
    I don't know whether there is a better solution


Log in to reply
 

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