Max Area of Island
Max Area of Island: in a binary grid where 1 is land, return the size of the largest 4-directionally connected island, or 0 if there is none.
- m == grid.length, n == grid[i].length
- 1 <= m, n <= 50
- grid[i][j] is either 0 or 1
Intuition
Each island is a connected component, so a flood fill from any unvisited land cell reaches exactly that island and nothing else. Letting the fill return the number of cells it consumed turns component discovery into area measurement in the same traversal. Sinking each visited cell to 0 as it is counted prevents revisits, which is what keeps the whole sweep linear in the grid size.
Connected components in a grid mean flood fill — DFS, BFS, or union-find. The variation is only what the fill computes: a count here, a perimeter elsewhere, a boolean for reachability. Number of Islands and Surrounded Regions share the identical sweep.
Approach
Before reading on: decide at exactly which point a cell must be marked visited, and construct the failure that occurs if you mark it after recursing. Then work out why the total cost stays linear despite launching a fill from many cells.
One flood fill per component
Sweep every cell. When an unvisited land cell is found, it must belong to an island not yet measured, so launch a depth-first fill from it. The fill explores the four orthogonal neighbours, and because it only ever moves through land, it terminates exactly at the island's boundary. Every land cell is therefore the starting point of at most one fill and is visited by exactly one fill overall, which is why the outer sweep plus all fills together cost O(rows × cols) rather than anything quadratic.
Returning area from the recursion
Define the fill to return an integer: 0 when the coordinate is out of bounds or is water, otherwise 1 + fill(up) + fill(down) + fill(left) + fill(right). The single 1 counts the current cell and the four recursive results accumulate the rest of the component. This is cleaner than threading a mutable counter through the recursion, and it makes the base case explicit — an out-of-range or water cell contributes nothing, which is precisely what stops the recursion.
Sinking cells, and the recursion depth
Set grid[r][c] = 0 immediately on entering a land cell, before recursing. Doing it after the recursive calls allows a neighbour to re-enter the same cell and recurse back, producing infinite recursion. Sinking in place removes the need for a separate visited matrix and keeps auxiliary space to the call stack alone. That stack can reach O(rows × cols) on a grid that is entirely land — at the 50×50 limit this is safe, but on much larger grids an explicit stack or BFS queue would be the safer choice.
Solution & live demo
Common pitfalls
Sinking the cell after the recursive calls
area = 1 + fill(r-1, c) + ... grid[r][c] = 0 return area
grid[r][c] = 0 return 1 + fill(r-1, c) + ...
A neighbour recurses back into this still-land cell, which recurses into the neighbour again, and the two bounce until the stack overflows. Marking before descending is what makes the traversal terminate.
Bounds checked after the grid access
if grid[r][c] == 0 or r < 0 or r >= rows:
return 0if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
return 0Python evaluates left to right, so grid[r][c] runs first and a negative index silently wraps to the far edge of the grid, joining unrelated islands. In C++ it reads out of bounds outright.
Counting diagonal neighbours as connected
for dr in (-1,0,1):
for dc in (-1,0,1):the four orthogonal directions only
The problem defines islands as 4-directionally connected. Including diagonals merges islands that should be separate and overstates the maximum area.
Edge cases
No fill ever launches and 0 is returned.
A single fill counts every cell; recursion depth equals the cell count.
Each is measured and the maximum is unchanged by ties.
Diagonals are not connections, so those are separate islands.
The fill returns 1 with all four neighbours out of bounds or water.