Max Area of Island

Imagine you are looking at a satellite photo of an ocean dotted with small islands. Your job is to fly a drone over the entire photo, and whenever you spot a piece of land you have not visited yet, you send the drone to explore that entire island before moving on.

The drone explores by landing on a land cell, then checking all four neighbors (up, down, left, right). If a neighbor is also land and has not been visited, the drone flies there next and repeats the process. Each time the drone visits a cell, it adds one to the island's area count.

To keep track of which cells the drone has already visited, we maintain a separate visited matrix — a grid of the same size filled with true/false values. Before exploring any cell, we check the visited matrix. After exploring, we mark it as visited.

After the drone finishes exploring one island, we record its area and move on. We scan every cell in the grid, and whenever we find an unvisited land cell, we launch a new exploration. At the end, the largest area we recorded is the answer.

This approach uses Depth-First Search (DFS) — the drone goes as deep as possible in one direction before backtracking. The visited matrix ensures we never count a cell twice.

Let's trace through with a smaller grid for clarity:

grid = [[0,1,0],
        [1,1,0],
        [0,0,1]]

We also create a visited matrix of the same size, initialized to all false.

Step 1: Start scanning from cell (0,0). Value is 0 (water). Skip it.

Step 2: Move to cell (0,1). Value is 1 (land) and not visited. Launch DFS from (0,1). Mark (0,1) as visited. Current island area = 1.

Step 3: DFS explores neighbors of (0,1). Check up (out of bounds), down (1,1) is land and unvisited → recurse. Mark (1,1) as visited. Area = 2.

Step 4: DFS from (1,1). Check up (0,1) — already visited. Check down (2,1) — value 0, water. Check left (1,0) — value 1, unvisited → recurse. Mark (1,0) as visited. Area = 3.

Step 5: DFS from (1,0). Check up (0,0) — water. Check down (2,0) — water. Check left — out of bounds. Check right (1,1) — already visited. No more unvisited neighbors. Backtrack. Island A complete with area = 3.

Step 6: Update max_area = max(0, 3) = 3. Continue scanning. Cell (0,2) is water, (1,0) visited, (1,1) visited, (1,2) water, (2,0) water, (2,1) water.

Step 7: Reach cell (2,2). Value is 1 and unvisited. Launch DFS. Mark (2,2) visited. All neighbors are water or out of bounds. Island B area = 1.

Step 8: Update max_area = max(3, 1) = 3. Scanning complete.

Result: Maximum island area = 3.

1. Create a visited matrix of the same dimensions as grid, initialized to all false
2. Initialize max_area = 0
3. For each cell (r, c) in the grid:
   • If grid[r][c] == 1 and visited[r][c] == false:
     • Run DFS from (r, c) to compute the area of this island
     • Update max_area = max(max_area, area)
4. DFS function dfs(r, c):
   • If (r, c) is out of bounds, or grid[r][c] == 0, or visited[r][c] == true: return 0
   • Mark visited[r][c] = true
   • Return 1 + dfs(r-1, c) + dfs(r+1, c) + dfs(r, c-1) + dfs(r, c+1)
5. Return max_area

Time Complexity: O(m × n)

We iterate over every cell in the grid once during the main scan. Each cell is visited at most once by DFS because the visited matrix prevents re-exploration. The DFS for each cell does O(1) work (checking bounds and four neighbors). Across all DFS calls, each cell is processed at most once, giving a total of O(m × n).

Space Complexity: O(m × n)

We allocate a visited boolean matrix of size m × n, which is the dominant space cost. Additionally, the DFS recursion stack can grow up to O(m × n) in the worst case (when the entire grid is one large island shaped like a snake), though typically it is much smaller.

Instead of keeping a separate notebook to track which cells we have explored, we can mark them directly on the map itself. The idea is simple: when our drone visits a land cell, it "sinks" that cell by changing it from 1 to 0. This way, if any future exploration tries to visit the same cell, it will see water and stop — exactly the same effect as the visited matrix, but without any extra memory.

Think of it like a treasure hunter exploring islands on a paper map. Each time the hunter confirms they have fully explored a piece of land, they use an eraser to remove that land from the map. When scanning the map later, erased areas look like water, so the hunter naturally skips them.

The algorithm is identical to the brute force: scan every cell, launch DFS from unvisited land, count the area, and track the maximum. The only change is how we mark cells as visited — we flip them to 0 instead of using a boolean matrix.

This approach is preferred in interviews because it demonstrates space optimization awareness. The trade-off is that it modifies the input, which may not always be acceptable. If the original grid must be preserved, the visited matrix approach is the safer choice.

Let's trace through with the same grid:

grid = [[0,1,0],
        [1,1,0],
        [0,0,1]]

Step 1: Scan cell (0,0). Value is 0 (water). Skip.

Step 2: Scan cell (0,1). Value is 1 (land). Launch DFS. Sink (0,1) by setting grid[0][1] = 0. Area so far = 1.
Grid becomes: [[0,0,0],[1,1,0],[0,0,1]]

Step 3: DFS checks neighbors of (0,1). Down neighbor (1,1) is 1 → recurse. Sink (1,1): grid[1][1] = 0. Area = 2.
Grid becomes: [[0,0,0],[1,0,0],[0,0,1]]

Step 4: DFS from (1,1) checks neighbors. Left neighbor (1,0) is 1 → recurse. Sink (1,0): grid[1][0] = 0. Area = 3.
Grid becomes: [[0,0,0],[0,0,0],[0,0,1]]

Step 5: DFS from (1,0) checks all neighbors. Up (0,0) = 0, down (2,0) = 0, left = out of bounds, right (1,1) = 0 (already sunk). No unvisited land. Backtrack.

Step 6: DFS fully returns. Island A area = 3. Update max_area = 3. Continue scanning.

Step 7: Cells (0,2), (1,0), (1,1), (1,2), (2,0), (2,1) are all 0 now. Skip them all.

Step 8: Reach cell (2,2). Value is 1. Launch DFS. Sink it: grid[2][2] = 0. Area = 1. All neighbors are 0 or out of bounds.

Step 9: Island B area = 1. max_area = max(3, 1) = 3.

Result: Maximum island area = 3. The grid is now all zeros.

1. Initialize max_area = 0
2. For each cell (r, c) in the grid:
   • If grid[r][c] == 1:
     • Run DFS from (r, c) to compute the island area
     • Update max_area = max(max_area, area)
3. DFS function dfs(r, c):
   • If (r, c) is out of bounds or grid[r][c] == 0: return 0
   • Set grid[r][c] = 0 (sink this cell)
   • Return 1 + dfs(r-1, c) + dfs(r+1, c) + dfs(r, c-1) + dfs(r, c+1)
4. Return max_area

Time Complexity: O(m × n)

Every cell in the grid is visited at most twice: once during the main loop scan, and at most once during a DFS call. Once a cell is sunk to 0, it is never processed again. The total work across all DFS calls is proportional to the number of cells, giving O(m × n).

Space Complexity: O(m × n) worst case for the recursion stack

We eliminated the visited matrix, so no extra O(m × n) memory is allocated. However, the DFS recursion stack can still grow up to O(m × n) in the worst case — for example, a grid that is entirely land arranged in a snaking path. In practice, the stack depth is typically O(min(m, n)) for reasonably shaped islands.

If the original grid must be preserved (not modified), the brute force approach with the visited matrix is necessary. The in-place approach is preferred when mutation is acceptable, as it reduces auxiliary space to O(1).