Data Structure1 Practice12 Interview

Matrix / Grid

GuideCode Labs

Two-dimensional indexed data commonly treated as rows, columns, or an implicit graph. This guide turns that contract into deliberate Python operations, interview invariants, and a runnable practice loop.

Recognize it when

Consider Matrix / Grid when the prompt's constraints and required operations match this shape: Two-dimensional indexed data commonly treated as rows, columns, or an implicit graph.

On this page · Mental Model

Checking your account…

Mental Model

A Python matrix is a list of row lists. Coordinates are ordered pairs (row, column), and the two bounds are independent. A rectangular grid has a common column count; a ragged list requires a different bound for each row and must be named as such in the contract.

Coordinates and Rectangular Shape

Read grid[row][column]: first select a row, then a cell. For a nonempty rectangular grid, cache rows = len(grid) and columns = len(grid[0]). Guard the empty grid before reading row zero. A four-direction neighbor changes exactly one coordinate by one.

Allocate Independent Rows

[[0] * columns] * rows repeats references to the same inner list. Updating one cell then changes the corresponding column in every aliased row. A comprehension evaluates the row expression once per iteration and creates independent row objects.

Allocate Independent Grid Rows

Reference

def make_grid(rows, columns, value):
    return [[value for _ in range(columns)] for _ in range(rows)]

Practice

Implement make_grid(rows, columns, value). Return distinct row lists so mutating one cell never changes another row.

def make_grid(rows, columns, value):
    return [[value] * columns] * rows

Public tests

Verify rows do not alias

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

The Python list documentation(opens in a new tab) defines shallow copying: copying the outer list alone does not clone nested rows.

Traverse Grid Neighbors

Treat a grid as an implicit graph when movement rules define edges. Scan cells in row-major order; when an active cell is not visited, start a DFS or BFS and mark neighbors when discovered. Each cell enters one component traversal at most once, so the total work is O(rows × columns), not the number of starts multiplied by grid size.

Visit Each Grid Component

Reference

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

Practice

Implement grid_component_sizes(grid). Return four-direction 1-component sizes in row-major discovery order without mutating the grid.

def grid_component_sizes(grid):
    if not grid:
        return []
    return [sum(sum(row) for row in grid)]

Public tests

Verify four-direction components

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

Choose Matrix or Sparse Coordinates

Use a matrix when most positions exist and direct coordinate lookup matters. Use a set or dictionary of coordinates for a huge sparse plane, especially when only a small fraction of cells are active. Use an adjacency list when neighbors are arbitrary rather than derived from local coordinate moves.

Common Pitfalls

Swapping row and column bounds works on square examples and fails on rectangular grids.
Marking a cell only when removed from the frontier allows duplicate enqueues.
Mutating the input as visited state may violate the function’s ownership contract.
Copying only the outer list preserves row alias relationships.
Recursive flood fill can exceed Python’s recursion limit on a long component.

Explain It in an Interview

State the coordinate convention and whether diagonal movement exists. Define when a cell becomes visited and what the frontier contains. Explain O(rows × columns) by charging constant neighbor work to each cell once, and distinguish auxiliary frontier/visited space from any required output.

Visit Each Grid Component(opens in a new tab) isolates traversal mechanics. Number of Islands(opens in a new tab) requires recognizing the same implicit graph inside a larger prompt.

Python Version Note

Python 3.11+

The examples use standard Python containers and syntax available in the supported browser runtime; Matrix / Grid itself is taught as an interview abstraction.

Verify in Python docs

Complexity & Invariants

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

Operation	Average	Worst	Interview note
Core Matrix / Grid workflow	`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 demonstrated Matrix / Grid workflow.

Assumptions

Exact bounds depend on copying, slicing, insertion position, and whether a new result is materialized.
The bound counts the operations in Visit Each Grid Component and does not hide Python slicing, sorting, or copying.

Invariants Worth Saying Aloud

State the precise Matrix / Grid invariant before coding and preserve it after every update, traversal step, or recursive return.
A grid of local neighbor connections is an implicit graph; start one traversal for each unvisited active cell. This remains true after every accepted operation.
A cell is marked visited before being added to the frontier, so every active cell contributes to exactly one component. This remains true after every accepted operation.

When To Use Or Avoid Matrix / Grid

Use It When

Use Matrix / Grid when its representation directly supports the prompt's repeated query or update.
Use it when the invariant can be stated before coding and preserved after every operation.

Choose Another Tool When

Avoid it when a simpler Python sequence or mapping communicates the same contract with less state.
Avoid it when building the structure costs more time or space than the number of required queries can justify.

Common Pitfalls

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

Leaving the core transition unfinished

Placeholder code cannot preserve the Matrix / Grid invariant or satisfy the public contract.

Prevent it: Implement the smallest complete transition and run the public tests before adding optimizations.

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 central invariant

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

Prevent it: Keep this invariant visible while editing: State the precise Matrix / Grid invariant before coding and preserve it after every update, traversal step, or recursive return.

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 inside the loop

Handle empty state, duplicate values, aliasing, and serialization boundaries explicitly in tests.

Prevent it: Account for every slice, copy, sort, membership test, and container mutation 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: Number of Islands(opens in a new tab)

Reviewed References

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

Python More on Lists(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…

Matrix / Grid Code Labs

Mental Model

Coordinates and Rectangular Shape

Allocate Independent Rows

Public tests

Traverse Grid Neighbors

Public tests

Choose Matrix or Sparse Coordinates

Common Pitfalls

Explain It in an Interview

Python Version Note

Complexity & Invariants

Space

Assumptions

Invariants Worth Saying Aloud

When To Use Or Avoid Matrix / Grid

Use It When

Choose Another Tool When

Common Pitfalls

Leaving the core transition unfinished

Breaking the central invariant

Hiding Python work inside the loop

Related Practice

Related Interview Problems

Reviewed References