Solutions

# BFS, DFS or Union-Find to find connected components in a grid.
# graphs

# BFS - O(m*n) time, O(m*n) space
def maxAreaOfIsland(grid: list[list[int]]) -> int:
    res = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == 1:
                area = get_area(grid, r, c)
                res = max(res, area)
    return res

def get_area(grid: list[list[int]], r: int, c: int) -> int:
    from collections import deque

    q = deque()
    area = 0
    q.append((r,c))
    grid[r][c] = -1
    while len(q) > 0:
        r, c = q.popleft()
        area += 1
        if r < len(grid)-1 and grid[r+1][c] == 1:
            # mark cell as visited as soon as we add them to the queue to avoid duplicates
            grid[r+1][c] = -1
            q.append((r+1, c))
        if c < len(grid[0])-1 and grid[r][c+1] == 1:
            grid[r][c+1] = -1
            q.append((r, c+1))
        if r>0 and grid[r-1][c] == 1:
            grid[r-1][c] = -1
            q.append((r-1, c))
        if c>0 and grid[r][c-1] == 1:
            grid[r][c-1] = -1
            q.append((r, c-1))

    return area

# DFS - O(m*n) time, O(m*n) space
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
    seen = set()
    ROWS, COLS = len(grid), len(grid[0])
    area = 0

    def dfs(r,c):
        if r<0 or c<0 or r>=ROWS or c>=COLS or \
            (r,c) in seen or grid[r][c] != 1:
            return 0

        seen.add((r,c))
        return (1 + dfs(r+1,c) +
                    dfs(r, c+1) +
                    dfs(r-1, c) +
                    dfs(r, c-1))

    for r in range(ROWS):
        for c in range(COLS):
            if grid[r][c] == 1:
                area = max(area, dfs(r,c))
    return area