Pattern1 Practice7 Interview

Island Traversal

GuideCode Labs

Treat a grid as an implicit graph and traverse connected components using directional neighbors. Learn its decision rule, maintained state, Python cost model, and transfer from a focused drill to a full Interview Problem.

Recognize it when

Consider Island Traversal when the prompt's constraints and required operations match this shape: Treat a grid as an implicit graph and traverse connected components using directional neighbors.

On this page · Treat the Grid as an Implicit Graph

Checking your account…

Treat the Grid as an Implicit Graph

Each eligible cell is a vertex; orthogonal or diagonal coordinate offsets define edges. Generate neighbors on demand instead of building an adjacency list.

Launch Once per Component

Scan every cell. When an eligible cell is unseen, increment the component count and traverse everything reachable from it. Later scan positions in that island are already marked.

Trace One Island Frontier

Reference

def island_trace(grid,row,col):
    if not grid or grid[row][col]!=1: return []
    seen=set(); trace=[]; stack=[(row,col)]
    while stack:
        r,c=stack.pop()
        if (r,c) in seen: continue
        seen.add((r,c)); trace.append([r,c])
        neighbors=[(r-1,c),(r,c+1),(r+1,c),(r,c-1)]
        for nr,nc in reversed(neighbors):
            if 0<=nr<len(grid) and 0<=nc<len(grid[0]) and grid[nr][nc]==1 and (nr,nc) not in seen: stack.append((nr,nc))
    return trace

Practice

Implement island_trace(grid,row,col). Return visited [row,col] cells in DFS order using up,right,down,left neighbors; 1 is land.

def island_trace(grid,row,col):
    pass

Public tests

Visit orthogonal land once

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Mark Before Adding Neighbors

Mark a cell when it enters the stack or queue so two frontier cells cannot add it twice. Check row and column bounds before indexing, and preserve the grid if mutation is outside the contract.

Count Grid Components

Reference

def count_islands(grid):
    if not grid: return 0
    seen=set(); count=0
    for row in range(len(grid)):
        for col in range(len(grid[0])):
            if grid[row][col]!=1 or (row,col) in seen: continue
            count+=1; seen.add((row,col)); stack=[(row,col)]
            while stack:
                r,c=stack.pop()
                for nr,nc in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
                    if 0<=nr<len(grid) and 0<=nc<len(grid[0]) and grid[nr][nc]==1 and (nr,nc) not in seen:
                        seen.add((nr,nc)); stack.append((nr,nc))
    return count

Practice

Implement count_islands(grid). Return the number of orthogonally connected groups of 1 without mutating grid.

def count_islands(grid):
    pass

Public tests

Launch once per unseen component

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose DFS BFS or Disjoint Set

DFS and BFS are simplest for one static grid, both O(rows × columns). Disjoint set is useful when cells activate incrementally or connectivity queries repeat. BFS may hold a wide frontier; recursive DFS risks Python depth limits.

Explain It in an Interview

Say: “The grid is an implicit graph under these neighbor offsets. Every unseen land cell launches exactly one component traversal, and marking on discovery visits each cell once.” State whether diagonal contact connects islands.

Python Version Note

Python 3.11+

The examples use the standard Python syntax and containers supported by the browser Judge; the Island Traversal invariant is independent of a minor Python release.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Island Traversal decision loop	`O(rows * columns)`	`O(rows * columns)`	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.

Space

O(rows * columns) for the focused Visit Each Grid Component implementation.

Assumptions

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.
The bound includes real Python operations; no repeated slicing, linear list membership, or hidden sorting is treated as free.

Invariants Worth Saying Aloud

State the precise Island Traversal invariant before coding and preserve it after every update, traversal step, or recursive return.
Every scheduled cell belongs to the current component.
No visited cell is scheduled again.
A grid of local neighbor connections is an implicit graph; start one traversal for each unvisited active cell. Preserve this property after every transition.
A cell is marked visited before being added to the frontier, so every active cell contributes to exactly one component. Preserve this property after every transition.

When To Use Or Avoid Island Traversal

Use It When

Use Island Traversal when the prompt exposes the ordering, monotonicity, recurrence, or constraint that makes this decision safe.
Use it when every scheduled cell belongs to the current component.

Choose Another Tool When

Avoid Island Traversal when its decision rule cannot eliminate work or preserve the required state.
Avoid forcing the label onto a prompt whose simpler direct scan already meets the constraints.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Moving state without a proof

Applying the pattern without proving its ordering, monotonicity, or window invariant can silently miss valid candidates.

Prevent it: Write the decision rule beside the loop and verify it against Visit Each Grid Component before optimizing.

Avoid

def grid_component_sizes(grid):
    pass

Use instead

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

Where you will hit this: Visit Each Grid Component(opens in a new tab)

Breaking the maintained state

Treats diagonal cells as connected even though the component contract allows only four-direction neighbors.

Prevent it: Use the public tests and preserve this state: Every scheduled cell belongs to the current component.

Avoid

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:
                r, c = stack.pop(); size += 1
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, -1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < columns and grid[nr][nc] == 1 and (nr, nc) not in visited:
                        visited.add((nr, nc)); stack.append((nr, nc))
            sizes.append(size)
    return sizes

Use instead

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

Where you will hit this: Visit Each Grid Component(opens in a new tab)

Hiding Python work in the hot path

Python slicing, copying, membership in lists, or repeated sorting inside the loop can invalidate the intended complexity.

Prevent it: Count every slice, copy, sort, membership check, and container update before claiming O(rows * columns).

Avoid

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:
                r, c = stack.pop(); size += 1
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, -1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < columns and grid[nr][nc] == 1 and (nr, nc) not in visited:
                        visited.add((nr, nc)); stack.append((nr, nc))
            sizes.append(size)
    return sizes

Use instead

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

Where you will hit this: Max Area of Island(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python collections.deque(opens in a new tab)
python-docs · checked 2026-07-12
Python deque Recipes(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…