158. Number of Islands

Scan the grid. Every fresh '1' you land on is an island — start there and flood-fill outwards, marking every connected land cell visited so you don't count the same island twice.

Approach

1. For each cell (r, c):
   • If grid[r][c] == '1', increment count and DFS from (r, c).
2. DFS sets grid[r][c] = '0' (or uses a visited set) and recurses into the four neighbors.

from collections import deque

def numIslands(grid):
    if not grid:
        return 0
    m, n = len(grid), len(grid[0])
    visited = set()
    count = 0
    for r in range(m):
        for c in range(n):
            if grid[r][c] == '1' and (r, c) not in visited:
                count += 1
                queue = deque([(r, c)])
                visited.add((r, c))
                while queue:
                    i, j = queue.popleft()
                    for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        ni, nj = i + di, j + dj
                        if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == '1' and (ni, nj) not in visited:
                            visited.add((ni, nj))
                            queue.append((ni, nj))
    return count

Same flood-fill idea as DFS, but iterative — a queue replaces the recursion stack. The big practical win: on a long thin grid (say 1×10000) DFS would blow Python's recursion limit, while BFS stays comfortable.

The flood-fill model

The grid is a graph where every '1' cell is a node and edges connect 4-directionally adjacent '1' cells. Counting islands means counting connected components of '1's.

We sweep the grid; every untouched '1' we land on is a brand-new component. Run BFS from there to mark all of its cells visited (so the outer sweep won't double-count).

Steps

1. Sweep (r, c) over every cell of the grid.
2. If grid[r][c] != '1', skip.
3. Otherwise, increment count, then start BFS:
   • queue = deque([(r, c)]). Mark visited by setting grid[r][c] = '0' (rewriting the grid avoids needing a separate visited set).
   • While the queue is non-empty: pop (i, j), and for each of the four neighbour offsets, if the neighbour is in bounds and equals '1', mark it '0' and enqueue it.
4. Return count.

Walk-through

Grid:

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

Outer sweep:

• (0, 0) = '1': count = 1. BFS marks the top-left 2×2 block as '0'.
• (0, 1) already '0'. Skip.
• … skip until …
• (2, 2) = '1': count = 2. BFS marks just (2, 2).
• (3, 3) = '1': count = 3. BFS marks (3, 3) and (3, 4) (they're connected horizontally).

Final count: 3. ✓

Why we mark visited inside the inner loop, before enqueuing

If we waited to mark visited until popping a cell, the same cell could be enqueued multiple times (once by each of its neighbours), wasting time and possibly running out of memory on dense grids. Marking at enqueue time guarantees each cell enters the queue at most once.

Why O(min(m, n)) space

In the worst case the BFS frontier (the queue's max size at any moment) is bounded by the perimeter of the explored region, which on an m × n grid is O(min(m, n)). DFS, in contrast, can recurse to depth m × n for a snaky island.

Edge cases

• Empty grid: the outer loop never enters; return 0.
• All water: every cell is '0'; return 0.
• All land: one giant island; one BFS visits every cell, count = 1.

Complexity

• Time: O(m · n) — every cell is checked at most a constant number of times across the BFS and the outer sweep.
• Space: O(min(m, n)) for the BFS queue.