Max Area of Island

Medium#695grid

You get a map of land and water cells. Land cells that touch by a side form one island, and its area is the number of its cells. Find the area of the biggest island, or 0 if there is no land. Our map has 4 rows: # # . #, . . # ., . # # #, # . # . (# is land) — the answer is 5: the plus in the middle; the other islands have 2, 1 and 1 cells.

695 Max Area of IslandWalkthrough · 1×

Example: find the biggest island on a map where it is found third and branches out in three directions from its centre.

01230123~~~~~~~best = 0call stacktop on the right—
land, not measured yetwater from the starton the call stack, size so far insidecurrent cellland next to it, measured nextturned into water, ↑ the area its call returned

No island measured yet: best = 0

01/68
restart · back · play · step
Speed
1function maxArea(grid):
2 best = 0
3 for each cell (row, col), row by row:
4 if grid[row][col] is land:
5 best = max(best, area(row, col))
6 return best
7
8function area(r, c):
9 grid[r][c] = water // so it is counted once
10 size = 1
11 for each land neighbour (nr, nc):
12 size = size + area(nr, nc)
13 return size
state
best
0
row
–
col
–
r
–
c
–
size
–
nr
–
nc
–
click a step to go back

← → step · space play/pause

Why it works

  1. The area of the land reachable from a cell is 1 for the cell plus the areas reachable from its land neighbours, so each call adds up what its calls return.
  2. A cell becomes water as soon as a call enters it, so no other call counts it twice, even where branches of an island meet.
  3. Each island is measured whole by one call from the scan, so comparing those results with best finds the biggest.

Complexity

Time O(rows × cols): each cell is scanned once and each land cell is entered once. Memory O(rows × cols) at worst, for a call stack as deep as one long island.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.