827. Making A Large Island

precompute each connected area then check 4-neighbor of each 0

Option 1: union find

time: O(m * n) suppose O(1) for find() and union()

class Solution:
    def __init__(self):
        self.parent = {}
        self.size = {}
    
    def largestIsland(self, grid: List[List[int]]) -> int:
        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        m, n = len(grid), len(grid[0])
        candidates = []
        maxArea = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    for dx, dy in DIRS:
                        nx, ny = i + dx, j + dy
                        if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
                            self.union(i, j, nx, ny)
                    rootX, rootY = self.find(i, j)
                    maxArea = max(maxArea, self.size[(rootX, rootY)])
                else:
                    candidates.append((i, j))
        
        for i, j in candidates:
            groupSet = set()
            groupSize = 1
            for dx, dy in DIRS:
                nx, ny = i + dx, j + dy
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
                    rootX, rootY = self.find(nx, ny)
                    if (rootX, rootY) not in groupSet:
                        groupSet.add((rootX, rootY))
                        groupSize += self.size[(rootX, rootY)]
            maxArea = max(maxArea, groupSize)
        return maxArea
    
    def find(self, x: int, y: int) -> tuple:
        if (x, y) not in self.parent:
            self.parent[(x, y)] = (x, y)
            self.size[(x, y)] = 1
        
        while (x, y) != self.parent[(x, y)]:
            x, y = self.parent[self.parent[(x, y)]]  
        
        return (x, y)
    
    def union(self, x1: int, y1: int, x2: int, y2: int) -> None:
        root1X, root1Y = self.find(x1, y1)
        root2X, root2Y = self.find(x2, y2)
        if root1X != root2X or root1Y != root2Y:
            size1 = self.size[(root1X, root1Y)]
            size2 = self.size[(root2X, root2Y)]
            if size1 < size2:
                self.parent[(root1X, root1Y)] = (root2X, root2Y)
                self.size[(root2X, root2Y)] += size1
            else:
                self.parent[(root2X, root2Y)] = (root1X, root1Y)
                self.size[(root1X, root1Y)] += size2

Option 2: dfs

time: O(m * n)

step one: calculate area of each group. to identify which group a cell belongs to, we use groups map map a cell to self-increase group_ID
connect groups by changing 0 to 1

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return 0

        n = len(grid)
        groups = {} # map each cell to a group id
        areas = {} # map group id to area of the group
        group_id = 0 # initialize group id
        res = 0

        # first pass to calcualte area of each group
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1 and (i, j) not in groups:
                    area = self.dfs(grid, i, j, group_id, groups)
                    areas[group_id] = area
                    res = max(res, area)
                    group_id += 1
        
        # second pass to change an 0 to 1
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 0:
                    connected_groups = set()
                    area = 1
                    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                        new_row, new_col = i + dr, j + dc
                        if (new_row, new_col) in groups and groups[(new_row, new_col)] not in connected_groups:
                            group_id = groups[(new_row, new_col)]
                            connected_groups.add(group_id)
                            area += areas[group_id]
                    res = max(res, area)
        return res
        
    def dfs(self, grid, row, col, group_id, groups):
        n = len(grid)
        groups[(row, col)] = group_id
        area = 1
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            new_row, new_col = row + dr, col + dc
            if 0 <= new_row < n and 0 <= new_col < n and grid[new_row][new_col] == 1 and (new_row, new_col) not in groups:
                area += self.dfs(grid, new_row, new_col, group_id, groups)
        return area

827. Making A Large Island - cocoder39/coco39_LC GitHub Wiki