48. Number of Islands (Connected GPU Regions)

Problem

A cluster health check produces a 2D grid of node statuses, one cell per physical node slot: 'H' for a healthy node, 'X' for one that's down or unreachable. A job that needs contiguous, directly-connected nodes (up, down, left, right — no diagonals) can only be scheduled onto one connected region of healthy nodes at a time. Given the grid, count how many separate connected healthy regions exist, so the scheduler knows how many independently-placeable "islands" of capacity it has to offer.

Source: src/48_number_of_islands.py

def count_connected_regions(grid: list[list[str]]) -> int: ...

>>> count_connected_regions([["H", "H", "X"], ["H", "X", "X"], ["X", "X", "H"]])
2

>>> count_connected_regions([["X", "X"], ["X", "X"]])
0

Step-by-Step Approach

1. Guard the empty-grid case ([] or a grid with no columns) and return 0 immediately.
2. Allocate a visited grid of the same shape, initialized to False, so each healthy cell is only ever counted once.
3. Scan every cell in row-major order. Whenever an unvisited 'H' cell is found, it must be the FIRST cell discovered in a brand-new connected region — flood- fill outward from it to mark the entire region visited, then increment the region counter exactly once.
4. The flood fill itself (BFS or DFS, either works) explores the 4 orthogonal neighbors of each cell it visits, only continuing into neighbors that are in-bounds, unvisited, and 'H'.
5. After the fill returns, every cell in that region is marked visited, so the outer scan will skip right over them — the next unvisited 'H' the scan finds is guaranteed to belong to a different region.
6. Return the final region counter.

The key insight is that "one flood-fill call = one connected region": the outer loop never needs to know a region's size or shape in advance, because starting a fill from any unvisited healthy cell and marking everything reachable from it is exactly equivalent to discovering that whole region in one shot.

Reference solution

def count_connected_regions(grid: list[list[str]]) -> int:
    # flood-fill (BFS/DFS) each unvisited 'H': every fill sinks one whole
    # region, so the count of fills IS the region count. O(rows * cols) time/space.
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    regions = 0

    def _flood_fill(start_r: int, start_c: int) -> None:
        stack = [(start_r, start_c)]
        visited[start_r][start_c] = True
        while stack:
            r, c = stack.pop()
            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 not visited[nr][nc] and grid[nr][nc] == "H":
                    visited[nr][nc] = True
                    stack.append((nr, nc))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "H" and not visited[r][c]:
                _flood_fill(r, c)
                regions += 1  # one fill consumes exactly one connected region

    return regions

Key Functions & Tricks

• Explicit stack-based DFS instead of recursive DFS — avoids Python's recursion-depth limit on a large or long, snaking region.
• visited grid — the mechanism that guarantees each cell (and thus each region) is only ever processed once.
• 4-directional delta tuples (dr, dc) — a compact way to enumerate orthogonal neighbors without four separate if-statements.
• Marking a cell visited at PUSH time (not pop time) — prevents the same cell from being added to the stack multiple times by different neighbors before it's processed.
• Counting fills, not cells — the region counter increments once per _flood_fill call, regardless of how large that region turns out to be.

How to Recognize This Pattern