Max Area of Island

Max Area of Island is the classic grid flood-fill problem. It teaches the move you reach for on any 2D grid: walk the grid, and whenever you find an unvisited region, flood-fill it with DFS to measure how big it is.

The slow way first

You might try to be clever and reason about shapes, but there is no shortcut around actually visiting the land. The real question is: when I stand on a land cell, how do I measure the whole island it belongs to without counting any cell twice?

If you do not mark cells as visited, a naive walk will revisit the same land over and over and either loop forever or massively overcount. The fix is simple and is the heart of the technique: mark each land cell the moment you count it.

The idea: flood-fill each island with DFS

Scan every cell. When you land on a 1 you have not seen, start a DFS from it. The DFS counts the current cell, marks it visited (overwrite it to 0), then recurses into its four neighbors, summing whatever area they return. Water and out-of-bounds cells return 0. The total is that island area; compare it against the running max.

The key insight: overwriting a counted cell to 0 doubles as the visited marker, so the same DFS naturally stops at the island edges and never recounts a cell.

Walk through it

Step through the animation. The scan hits land at (0,0) and launches a DFS. Watch each visited cell flip and the area counter climb to 4 as the flood-fill expands down and right. When the neighbors run out, the DFS returns 4 and max updates. The scan then finds a separate 1-cell island, but max stays 4.

Pseudocode

best = 0
for each cell (r, c) in the grid:
    if grid[r][c] is land (1):
        best = max(best, dfs(r, c))     # measure this island
return best
 
dfs(r, c):
    if (r, c) is off-grid or water (0):
        return 0
    grid[r][c] = 0                       # mark visited so we never recount
    area = 1                             # count this cell
    for each of the 4 neighbors:
        area += dfs(neighbor)            # add the connected land
    return area

The Python solution

def max_area_of_island(grid):
    best = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == 1:
                best = max(best, dfs(grid, r, c))
    return best
 
def dfs(grid, r, c):
    if not in_bounds(grid, r, c) or grid[r][c] == 0:
        return 0
    grid[r][c] = 0
    area = 1
    for nr, nc in neighbors(r, c):
        area += dfs(grid, nr, nc)
    return area

• The double loop scans every cell; we only start a DFS when we hit a land cell.
• best = max(best, dfs(...)) keeps the largest island area seen so far.
• In dfs, the first if is the base case: off-grid or water returns 0, ending that branch.
• grid[r][c] = 0 marks the cell visited and counts as overwriting it, so it is never visited again.
• area = 1 counts the current cell; we then add the area returned by each of the four neighbor DFS calls.

Complexity

Every cell is touched a constant number of times, so the whole thing is O(m·n). The extra space is the recursion stack, which in the worst case (one giant snaking island) can reach O(m·n).

When this pattern shows up

Practice