Problem Statement

You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical). You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Additional information

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] is either 0 or 1.

Example 1:

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]

Output: 6

Explanation: The answer is not 11, because the island must be connected 4-directionally. The largest island has an area of 6.

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]

Output: 0

Recursive Depth-First Search (DFS)

Intuition

This problem is extremely similar to finding the "Number of Islands". The main difference is that instead of just counting how many islands exist, we need to count how many cells make up each individual island, and keep track of the largest one we've seen so far.

We can iterate through every cell in the grid. When we find a 1 (land), we trigger a Depth-First Search (DFS). The DFS will explore the island, change every visited piece of land to a 0 (so we don't count it again), and return the total number of cells it found in that specific island. We compare this area to our running max_area and keep the larger value.

Algorithm

1. Store the dimensions ROWS and COLS of the grid.
2. Initialize a variable max_area = 0.
3. Create a recursive helper function dfs(r, c) that returns an integer (the area).
4. Base Cases: If r or c are out of bounds, or if grid[r][c] == 0, return 0 (this branch adds 0 area).
5. Sink the land: Change grid[r][c] = 0 to mark it as visited.
6. Recurse and Sum: The area of the current cell is 1. Add this to the recursive calls of its 4 neighbors: 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1).
7. Return this calculated sum.
8. Loop through every row r and column c. If grid[r][c] == 1, calculate current_area = dfs(r, c) and update max_area = max(max_area, current_area).
9. Return max_area.

def max_area_of_island(grid: list[list[int]]) -> int:
    ROWS, COLS = len(grid), len(grid[0])
    max_area = 0
    
    def dfs(r, c):
        if r < 0 or r >= ROWS or c < 0 or c >= COLS or grid[r][c] == 0:
            return 0
            
        # Mark as visited by sinking the island
        grid[r][c] = 0
        
        # Current cell contributes 1 to the area, plus the area of neighbors
        return (1 + 
                dfs(r + 1, c) + 
                dfs(r - 1, c) + 
                dfs(r, c + 1) + 
                dfs(r, c - 1))
                
    for r in range(ROWS):
        for c in range(COLS):
            if grid[r][c] == 1:
                max_area = max(max_area, dfs(r, c))
                
    return max_area

Time & Space Complexity

• Time complexity: O(M * N)

• Reason: M is the number of rows and N is the number of columns. Every cell in the grid is visited exactly once by the main loop and at most once by the DFS before it is converted to 0.

• Space complexity: O(M * N)

• Reason: In the worst-case scenario (where the entire grid is a single connected island), the recursion stack for the DFS will go M * N levels deep.

Iterative Breadth-First Search (BFS)

Intuition

Just like with other grid problems, recursive DFS can run into stack overflow limits on incredibly massive grids. We can perform the exact same area calculation using an iterative Breadth-First Search (BFS) with a Queue.

When we find a 1, we initialize an area counter to 1, add the cell's coordinates to our queue, and sink it. Then, while the queue is not empty, we pop a cell, check its 4 neighbors, and for every neighbor that is a 1, we increment our area counter, sink the neighbor, and add it to the queue.

Algorithm

1. Store the dimensions ROWS and COLS. Initialize max_area = 0.
2. Create an iterative helper function bfs(r, c) that returns the area.
3. Initialize a deque (queue) with [(r, c)] and set grid[r][c] = 0.
4. Initialize an area variable to 1.
5. While the queue has elements:

• Pop the front coordinates row, col.
• Check all 4 adjacent directions.
• If a neighbor is within bounds and is 1:
• Add it to the queue.
• Instantly mark it as 0 to prevent other neighbors from queuing it twice.
• Increment area by 1.

6. Return the area.
7. Loop through every cell. If it's a 1, call bfs(r, c) and update max_area.
8. Return max_area.

def max_area_of_island(grid: list[list[int]]) -> int:
    ROWS, COLS = len(grid), len(grid[0])
    max_area = 0
    
    def bfs(r, c):
        q = deque()
        q.append((r, c))
        grid[r][c] = 0
        area = 1
        
        while q:
            row, col = q.popleft()
            directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
            
            for dr, dc in directions:
                nr, nc = row + dr, col + dc
                if 0 <= nr < ROWS and 0 <= nc < COLS and grid[nr][nc] == 1:
                    q.append((nr, nc))
                    grid[nr][nc] = 0
                    area += 1
                    
        return area
        
    for r in range(ROWS):
        for c in range(COLS):
            if grid[r][c] == 1:
                max_area = max(max_area, bfs(r, c))
                
    return max_area

Time & Space Complexity

• Time complexity: O(M * N)

• Reason: Every cell is processed at most twice.

• Space complexity: O(min(M, N))

• Reason: The queue holds the perimeter of the island as BFS expands outwards layer by layer. The maximum size of this queue is bounded by the diagonal length of the grid, taking up O(min(M, N)) auxiliary space, making it much more memory efficient than DFS on large grids.