LeetCode 200 Number of Islands - Example and Complexity Analysis

Trace the example grid.

Scan (0,0): '1'. Start BFS. Visit (0,0), (0,1), (1,0), (1,1). Mark all as visited. Island count = 1.

Scan (0,2): '0'. Skip.

...continue scanning...

Scan (2,2): '1'. Start BFS. Visit (2,2) only (no adjacent land). Island count = 2.

Scan (3,3): '1'. Start BFS. Visit (3,3), (3,4). Island count = 3.

Done. Return 3.

Each cell visited at most twice (scan + BFS). $O(m \cdot n)$ time. $O(\min(m, n))$ space for BFS queue in worst case.