Python Union-Find solution without using Set


  • 0
    Z

    Use "root point" instead of set to record an area of connected land. Every point can trace its "root" by looking up a chained dictionary, which works like a linked list.

    def numIslands2(self, m, n, positions):
        """
        :type m: int
        :type n: int
        :type positions: List[List[int]]
        :rtype: List[int]
        """
        
        chainmap = {}
        
        def getNeighbors(i, j):
            return [(ii, jj) for (ii, jj) in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)) \
                    if (ii, jj) in chainmap]
        
        def getRoot(point):
            p = point
            while chainmap[p] != p:
                p = chainmap[p]
            chainmap[point] = p # memorize for future fast trace
            return p
        
        ret = []
        nroots = 0
        for (i, j) in positions:
            hasRoot = False
            rootToMerge = []
            for neighbor in getNeighbors(i, j):
                root = getRoot(neighbor)
                if not hasRoot:
                    chainmap[(i, j)] = root
                    hasRoot = True
                else:
                    newroot = chainmap[(i, j)]
                    if root not in rootToMerge and root != newroot:
                        rootToMerge.append(root)
                        chainmap[root] = newroot
                        nroots -= 1
            if (i, j) not in chainmap:
                chainmap[(i, j)] = (i, j)
                nroots += 1
            ret.append(nroots)
            
        return ret

Log in to reply
 

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