TL;DR
Flood-fill each island and track the largest, using DFS or BFS over the grid graph. Runs in O(m·n) time; union-find is an equivalent alternative.
Approach 1 — DFS flood fill
A grid is an implicit graph: each land cell links to its 4 orthogonal land neighbors, and an island is a connected component. For the example grid [[1,1,0],[1,0,0],[0,0,1]], the land cells form two components:
graph LR
A["(0,0)"] --- B["(0,1)"]
A --- C["(1,0)"]
D["(2,2)"]
The first component has 3 cells; the second is a singleton. The answer is the size of the largest component.
Scan every cell; on an unvisited 1, DFS floods the whole component and returns its cell count. Mark cells visited (here by sinking them to 0) so each is counted once. Keep the max over all islands.
def maxAreaOfIsland(grid: list[list[int]]) -> int:
rows, cols = len(grid), len(grid[0])
def dfs(r: int, c: int) -> int:
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
return 0
grid[r][c] = 0 # sink so we never revisit
return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)
best = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
best = max(best, dfs(r, c))
return best
Walkthrough (grid = [[1,1,0],[1,0,0],[0,0,1]]):
- First
1 at (0,0): DFS sinks (0,0), spreads to (1,0) and (0,1), each dead-ending → area 3. best = 3.
- Next unsunk
1 at (2,2): isolated → area 1. best = max(3,1) = 3.
- Return
3.
Complexity: every cell is visited a constant number of times → O(m·n) time. Space is O(m·n) worst case for the recursion stack (a snake-shaped island).
Approach 2 — BFS flood fill
Same component-flooding, but with an explicit queue instead of recursion. This matters when an island could be up to 2500 cells (50×50): a snake-shaped island would recurse deeper than Python’s default recursion limit (1000), whereas BFS holds the frontier in an explicit queue and has no depth limit. DFS is shorter; BFS is the safer choice for large grids. This version uses a separate visited set to leave grid intact.
from collections import deque
def maxAreaOfIsland(grid: list[list[int]]) -> int:
rows, cols = len(grid), len(grid[0])
visited = set()
def bfs(sr: int, sc: int) -> int:
queue = deque([(sr, sc)])
visited.add((sr, sc))
area = 0
while queue:
r, c = queue.popleft()
area += 1
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if (
0 <= nr < rows
and 0 <= nc < cols
and grid[nr][nc] == 1
and (nr, nc) not in visited
):
visited.add((nr, nc))
queue.append((nr, nc))
return area
best = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1 and (r, c) not in visited:
best = max(best, bfs(r, c))
return best
Walkthrough (same grid): BFS from (0,0) enqueues neighbors (1,0) and (0,1); popping them adds no new land → area 3. Later (2,2) floods alone → area 1. best = 3.
Complexity: O(m·n) time, O(m·n) space for visited and the queue.
Approach 3 — Union-find
Give each land cell an id, then union it with its right and down land neighbors (checking those two directions suffices to connect every adjacent pair). Each disjoint set is one island; track a size array during union so the answer is the largest set. Union-find (disjoint-set union) is most useful when islands are merged incrementally; for a static grid it ties DFS/BFS.
def maxAreaOfIsland(grid: list[list[int]]) -> int:
rows, cols = len(grid), len(grid[0])
parent = {}
size = {}
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra != rb:
if size[ra] < size[rb]:
ra, rb = rb, ra
parent[rb] = ra
size[ra] += size[rb]
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
parent[(r, c)] = (r, c)
size[(r, c)] = 1
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
if r + 1 < rows and grid[r + 1][c] == 1:
union((r, c), (r + 1, c))
if c + 1 < cols and grid[r][c + 1] == 1:
union((r, c), (r, c + 1))
return max(size.values(), default=0)
Walkthrough (same grid): cells (0,0),(0,1),(1,0) union into one set of size 3; (2,2) stays a singleton size 1. max(size.values()) = 3.
Complexity: O(m·n · α(m·n)) ≈ O(m·n) time with path compression + union by size, O(m·n) space.
Common pitfalls
- Counting diagonal neighbors — connectivity is 4-directional only.
- Forgetting to mark cells visited (or to sink them), which double-counts and can loop; sinking mutates the input, so use a
visited set if the caller needs grid preserved.
- Returning
0 incorrectly when the max should be found — initialize best = 0 so the all-water case returns 0 naturally.
- In union-find, unioning only one direction (say right) misses vertical adjacencies; you need both right and down.
Pattern takeaway
Grid problems are graph problems: cell = node, orthogonal neighbors = edges, island = connected component. Flood-fill (DFS or BFS) each unvisited component and aggregate the result, here the max size. Use BFS when recursion depth could exceed the stack limit on a large grid, DFS for concise code, and union-find when components merge dynamically or you need set sizes directly.