Python Union-Find, Detailed English Explanation


  • 0
    W

    The key idea is to make each land position in an island point to a "root" land position in that island. Also maintain a mapping from roots to all land positions in the island

    posToRoot = {}
    rootToPos = {}
    

    When a new land position has no neighboring island, initialize a new island and set the new land position to its root

    When a new land position has 1 neighboring island, make a new island with that position as the root

    When a new land position has 2+ neighboring islands, combine the multiple islands with multiple roots to have just one root

    from sets import Set
    
    class Solution(object):
        def numIslands2(self, m, n, positions):
            """
            :type m: int
            :type n: int
            :type positions: List[List[int]]
            :rtype: List[int]
            """
            def getNeighbors(i, j):
                # helper that gives list of indexes within m, n
                neighbors = []
                if i>0: neighbors.append((i-1, j))
                if j>0: neighbors.append((i, j-1))
                if i+1<m: neighbors.append((i+1, j))
                if j+1<n: neighbors.append((i, j+1))
                return neighbors
        
            def getNeighborRoots(i, j):
                # helper that returns list of roots for unique islands neighboring position i, j
                return list(Set([posToRoot.get(x, None) for x in getNeighbors(i, j) if posToRoot.get(x, None)]))
            
            posToRoot = {}
            rootToPos = {}
            res = []
        
            for i, j in positions:
                # for each new land position to add
    
                neighborRoots = getNeighborRoots(i, j)
                if not neighborRoots:
                    # no connected islands, make new island
                    rootToPos[(i, j)] = [(i, j)]
                    posToRoot[(i, j)] = (i, j)
                else: 
                    # has 1 or more connected islands
                    targetRoot = neighborRoots[0]
                    posToRoot[(i, j)] = targetRoot
                    rootToPos[targetRoot].append((i, j))
                    for i in range(1, len(neighborRoots)):
                        # if has more than 1 connected islands, combine
                        # extra islands into one single island
                        myroot = neighborRoots[i]
                        for pos in rootToPos[myroot]:
                            posToRoot[pos] = targetRoot
                            rootToPos[targetRoot].append(pos)
                        del rootToPos[myroot]
                res.append(len(rootToPos))
            return res
    

Log in to reply
 

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