leetcode-graph

305. Number of Islands II.py

class UnionFindSet(object):
    def __init__(self):
        """
        This is version, we don't know how many nodes we'll cope with in the begining. 
        So, we use dict to store _parents and _rank instead of array.
        Also, we would know nb of connected components dynamically.
        """
        self._parents = {}
        self._ranks = {}
        self.count = 0 # nb of connected components

    def add(self, p):
        self._parents[p] = p
        self._ranks[p] = 1
        self.count += 1

    def find(self, u):
        while u != self._parents[u]:
            self._parents[u] = self._parents[self._parents[u]]
            u = self._parents[u]
        return u

    def union(self, u, v):
        root_u, root_v = self.find(u), self.find(v)
        if root_u == root_v:
            # they're merge together, it won't affect current nb of connected components
            return True
        
        if self._ranks[root_u] > self._ranks[root_v]:
            self._parents[root_v] = root_u
        elif self._ranks[root_v] > self._ranks[root_u]:
            self._parents[root_u] = root_v
        else:
            self._parents[root_u] = root_v
            self._ranks[root_v] += 1
        self.count -= 1
        return False
    
class Solution:
    """
    Follow-up:
        Can you do it in time complexity O(l log mn), where l is the length of the positions?
    
    Thought Process:
        Brute Force:
            Leverage algorithm of numIslands one.
            For each add operation, we call api of numIslands one.
            In this way, running time is O(l*m*n), where l is number of operations.
        Union Find:
            We cannot iterate all the nodes(cells) because it won't meet the follow-up requirement.
            So, we iterate all land node. 
                step1:For each step, we try to merge neighbor node of current land node together if neighbor node is a land 
                by union method provided by unionfind data structure.
                step2: append current nb of connected component into ans array.
            Basically, our union find data struture only store node who is a land.            
    Note:
        1. we amend our union-find data structure to cope with we don't know how many nodes in the graph in the begining.
        2. we progressive merge then if they're land
        3. we amend our union-find data structure to count nb of connected component dynamically
    Reference:
        https://leetcode.com/problems/number-of-islands-ii/discuss/75459/JavaPython-clear-solution-with-UnionFind-Class-(Weighting-and-Path-compression)
    """
    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
        """
        T: O(l log(mn)) =~ O(l)
        S: O(mn) in wost case there every node is a land.
        """
        self.directions = [(0,1),(0,-1),(1,0),(-1,0)]
        ans = []
        islands = UnionFindSet()
        for land_node in map(tuple, positions):
            # p must be land
            if land_node not in islands._parents:
                # we try to merge the land together
                islands.add(land_node)
                for direction in self.directions:
                    nei_node = (land_node[0] + direction[0], land_node[1] +direction[1])
                    if nei_node in islands._parents:
                        islands.union(land_node, nei_node)
            ans.append(islands.count)
        return ans