[LeetCode] 827. Making A Large Island

 Problem : https://leetcode.com/problems/making-a-large-island/

Consider an island is a group, it is intuitive to use union-find to find the size of islands then find the maximum size of island when join 2 disconnected islands together.

class UnionFind:
    def __init__(self, n):
        self.group = [i for i in range(n)]
        self.usize = defaultdict(lambda:1)
        
    def union(self, a, b):
        ap = self.find(a)
        bp = self.find(b)
        
        if ap != bp:
            self.group[bp] = ap
            self.usize[ap] += self.usize[bp]
            self.usize[bp] = 0
        
    
    def find(self, a):
        b = self.group[a]
        
        while b != self.group[b]:
            b = self.group[b]
        
        while self.group[a] != b:
            tmp = self.group[a]
            self.group[a] = b
            a = tmp
        
        return b
    
    def sizeOf(self, a):
        ap = self.find(a)
        return self.usize[ap]
            

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        ROW = len(grid)
        COLUMN = len(grid[0])
        
        uf = UnionFind(ROW * COLUMN)
        
        for y in range(ROW):
            for x in range(COLUMN):
                # union the adjucent '1's
                for dy, dx in [(-1,0), (0,-1)]:
                    ny, nx = y + dy, x + dx
                    if 0 <= ny < ROW and 0 <= nx < COLUMN and grid[ny][nx] == 1 and grid[y][x] == 1:
                        uf.union(ny*COLUMN + nx, y*COLUMN + x)
        
        result = 0
        for y in range(ROW):
            for x in range(COLUMN):
                if grid[y][x] == 1:
                    result = max(result, uf.sizeOf(y*COLUMN + x))
                else:
                    tmp = {}
                    # connect the disjointed unions
                    for dy, dx in [(-1,0), (1,0), (0,-1), (0,1)]:
                        ny, nx = y + dy, x + dx
                        if 0 <= ny < ROW and 0 <= nx < COLUMN and grid[ny][nx] == 1:
                            p = uf.find(ny * COLUMN + nx)
                            tmp[p] = uf.sizeOf(p)
                    
                    result = max(result, sum(tmp.values()) + 1)
        
        return result