Description
Find the largest number of 1-cells connected horizontally or vertically in a rectangular binary grid. Diagonal contact does not connect islands; no land yields zero.
Solution
def max_area_of_island(grid):
rows, cols = len(grid), len(grid[0])
best = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != 1:
continue
stack = [(r, c)]
grid[r][c] = 0
area = 0
while stack:
x, y = stack.pop()
area += 1
for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1:
grid[nx][ny] = 0
stack.append((nx, ny))
best = max(best, area)
return bestExamples
Example 1
- Input
[[[0,1,1],[0,1,0],[1,0,1]]]- Output
3
The three top-right land cells form the largest island.
Example 2
- Input
[[[0,0],[0,0]]]- Output
0
There is no land.
Example 3
- Input
[[[1,1],[1,1]]]- Output
4
All four cells are connected.
Approach
Scan the grid. For each unvisited land cell, flood-fill its component using an explicit stack, marking cells when added. Count its size and keep the largest component.
Time & space
O(rc) time and O(rc) auxiliary space for r rows and c columns. This solution marks the input grid in place.