Graphs · Flood fill on a grid LeetCode 695

Max Area of Island / visualized

Problem 200 counts components; this one measures them. The scan, the four neighbours and the sink-before-you-recurse rule are unchanged — the single edit is the return type. void becomes int, and every call owes its caller 1 + down + up + right + left. The sum is assembled on the way down and collapses on the way back up; watch the returns land.

Grid (rows of 0/1, separated by /)

Execution

idle

Press Run to begin.

0 / 0

Speed

Java · running line

scan cursor call on top of the stack this island, already returned island finished water

A number inside a cell is what that call returned — the size of the piece of island it was responsible for. The cell that started the island therefore carries the island's whole area.

O(m·n) time · O(m·n) worst-case recursion depth · the 1 + is free: the visit that counted the island already existed, it just threw its result away. Sinking before the four calls is what keeps every cell in exactly one summand — a cell already sunk returns 0, so it is added once and never again.