Visit Each Grid Component

1. Step 1: Scan water with visited state

   Create a matching visited matrix and return no component sizes when every cell is water. Grid dimensions and visited ownership must be correct before a neighbor traversal mutates them.

2. Step 2: Flood one land component

   Use an explicit stack to visit all orthogonal land reachable from the first component seed. One component isolates bounds, water, and visited checks from the outer restart logic.

3. Step 3: Restart for every component

   Continue the outer row-major scan after each flood so disconnected and diagonal land produces separate sizes. Removing the teaching return turns one correct flood into complete component enumeration.

• Marking visited only when removing from the frontier can enqueue the same cell many times.
• Diagonal neighbors must not connect components under the four-direction contract.
• trees and graphs

• Python deque Recipes

• Max Area of Island(opens in a new tab)

  Visit Each Grid Component isolates a cell is marked visited before being added to the frontier, so every active cell contributes to exactly one component. That focused state discipline is required when implementing max area of island as a complete Interview Problem.

• Number of Islands(opens in a new tab)

  Visit Each Grid Component isolates a cell is marked visited before being added to the frontier, so every active cell contributes to exactly one component. That focused state discipline is required when implementing number of islands as a complete Interview Problem.

• Surrounded Regions(opens in a new tab)

  Visit Each Grid Component isolates a cell is marked visited before being added to the frontier, so every active cell contributes to exactly one component. That focused state discipline is required when implementing surrounded regions as a complete Interview Problem.

• Word Search II(opens in a new tab)

  Visit Each Grid Component isolates a cell is marked visited before being added to the frontier, so every active cell contributes to exactly one component. That focused state discipline is required when implementing word search two as a complete Interview Problem.

• Word Search in a Character Grid(opens in a new tab)

  Visit Each Grid Component isolates a cell is marked visited before being added to the frontier, so every active cell contributes to exactly one component. That focused state discipline is required when implementing word search as a complete Interview Problem.

A grid of local neighbor connections is an implicit graph; start one traversal for each unvisited active cell. A cell is marked visited before being added to the frontier, so every active cell contributes to exactly one component.

Why it works: Starting a traversal only from an unvisited active cell discovers exactly its four-direction reachable component. Early marking prevents duplicate discovery, and scanning all cells eventually starts every distinct component once.

def grid_component_sizes(grid):
    if not grid:
        return []
    rows, columns = len(grid), len(grid[0])
    visited = set()
    sizes = []
    for row in range(rows):
        for column in range(columns):
            if grid[row][column] != 1 or (row, column) in visited:
                continue
            stack = [(row, column)]
            visited.add((row, column))
            size = 0
            while stack:
                current_row, current_column = stack.pop()
                size += 1
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    neighbor = (current_row + dr, current_column + dc)
                    if 0 <= neighbor[0] < rows and 0 <= neighbor[1] < columns and grid[neighbor[0]][neighbor[1]] == 1 and neighbor not in visited:
                        visited.add(neighbor)
                        stack.append(neighbor)
            sizes.append(size)
    return sizes