A matrix is a two-dimensional array where each cell sits in a grid of rows and columns. Think of a chess board where each square has its own coordinates. We describe a matrix's size using two numbers: m for the number of rows and n for the number of columns, written as m × n.

# Creating a matrix (2D array) - O(m * n)
def createMatrix(rows: int, cols: int) -> List[List[int]]:
    return [[0] * cols for _ in range(rows)]

# Traversing all cells in a matrix - O(m * n)
def traverseMatrix(matrix: List[List[int]]) -> None:
    rows, cols = len(matrix), len(matrix[0])
    for r in range(rows):
        for c in range(cols):
            print(matrix[r][c])

# Four directions: up, down, left, right
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

Matrices are a great fit for problems about spaces and connections, like finding the shortest path through a maze or tracking how something spreads across a grid. Each cell can hold different types of information. In a maze, cells might represent walls, open paths, or visited locations. We can move through the matrix by changing our row and column position, typically going in four directions to reach neighboring cells.

Matrix operations come down to accessing, updating, and traversing cells in the grid. Since matrices use direct indexing, accessing any single cell is always constant time. The main cost comes from operations that visit multiple cells, which scale with the total number of cells, m × n.

The most basic way to process a matrix is to visit every cell using nested loops: one for rows, one for columns. This row-by-row traversal runs in O(m × n) time and is the foundation for most matrix algorithms. You'll use it for searching, counting, or transforming values across the entire grid.

When a problem only asks you to process a specific row, column, or diagonal, you can cut the work down by limiting your loop to that slice. For example, summing a single row is O(n) and summing a column is O(m), both much faster than scanning the whole grid.

Most matrix problems require moving from one cell to its neighbors. The standard approach is to define a directions array that stores the row and column offsets for each possible move. For cardinal movement (up, down, left, right), you use four direction pairs. When diagonals are allowed, you extend it to eight.

# Four cardinal directions: up, down, left, right
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# BFS traversal from a starting cell - O(m * n)
def bfs(matrix: List[List[int]], startRow: int, startCol: int) -> None:
    rows, cols = len(matrix), len(matrix[0])
    visited = set()
    visited.add((startRow, startCol))
    queue = deque([(startRow, startCol)])

    while queue:
        r, c = queue.popleft()
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append((nr, nc))

Before moving to a neighbor, always check that the new position is within the matrix bounds. This boundary check prevents out-of-bounds errors and is the single most common source of bugs in matrix problems. The pattern 0 <= nr < rows and 0 <= nc < cols should become second nature.

Depth-First Search on a matrix explores as far as it can in one direction before backtracking. Each cell acts like a node, and its four neighbors act like edges in a graph. DFS is the right tool for problems like counting islands, flood fill, or finding connected regions, where you want to fully explore one area before moving on.

# DFS traversal on a matrix - O(m * n)
def dfs(matrix: List[List[int]], r: int, c: int, visited: Set) -> None:
    rows, cols = len(matrix), len(matrix[0])
    if r < 0 or r >= rows or c < 0 or c >= cols:
        return
    if (r, c) in visited:
        return

    visited.add((r, c))

    # Explore four directions
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for dr, dc in directions:
        dfs(matrix, r + dr, c + dc, visited)

The recursive approach is the most natural way to implement DFS on a matrix. Each call checks bounds, marks the cell as visited, then recurses into all four neighbors. The call stack depth can reach O(m × n) in the worst case, so for very large grids, switch to an iterative version with an explicit stack.

Breadth-First Search on a matrix explores all neighbors at the current distance before moving further. BFS guarantees the shortest path in an unweighted grid, which makes it the go-to choice for problems like shortest path in a maze, rotting oranges, or multi-source distance calculations.

BFS uses a queue to process cells level by level. Start by adding the source cell to the queue and marking it visited. Then repeatedly dequeue a cell, check its four neighbors, and enqueue any valid unvisited ones. The time and space complexity are both O(m × n) since each cell is visited at most once.

Matrix problems show up constantly in coding interviews, often disguised as grid traversal, island counting, or pathfinding. Here are a few tips for tackling them:

Matrix problems are deceptively rich. The same grid can be a flood-fill canvas, a multi-source BFS battlefield, or a state-encoded cellular automaton. Work through these to internalize the patterns for direction vectors, in-place 2D mutation, and matrix backtracking: