Matrix Algorithms: Complete Guide with Grid Examples

Matrix algorithms show up in image processing, game boards, and dynamic programming tables. Any problem that hands you a 2D array is a matrix problem. The difference between a clean solution and a messy one is usually how carefully you manage the coordinates. A cell is addressed by two indices instead of one, and that small change creates its own techniques and its own bugs.

Definition: matrix algorithms are techniques for traversing, searching, and transforming two-dimensional arrays. The core skill is translating between a cell’s position and its contents safely. matrix[r][c] means row r, column c, and every neighbor access needs a bounds check.

Real-World Analogy

Think of a stadium seat. The ticket says Section 12, Row 7, Seat 14. A matrix is the two-dimensional version of that map. Every cell has a fixed address made of a row and a column. To find a specific seat you read the two numbers. To scan the whole section you walk row by row. To get from one seat to the next you change exactly one coordinate at a time.

Most matrix interview problems are about moving through that map in a disciplined way. The discipline is the algorithm. Walking every seat in order is traversal. Walking only the outer ring is spiral traversal. Rearranging the seats without moving them to a second map is an in-place transform like rotation. The grid is always the same. Only the route and the rearrangement rules change.

Visual Explanation

The single most important idea is the coordinate system. Every cell has a row index and a column index, and its four neighbors are one step away along one axis.

    graph TD
    A["matrix[r][c]"] --> B["Value at row r, column c"]
    A --> C["Neighbors"]
    C --> D["Up: matrix[r-1][c]"]
    C --> E["Down: matrix[r+1][c]"]
    C --> F["Left: matrix[r][c-1]"]
    C --> G["Right: matrix[r][c+1]"]
  

Notice that up and down change the row index while left and right change the column index. A common mistake is to read the indices as Cartesian x and y coordinates, where the first value is horizontal. In matrices the first index is always the row, which is vertical. Translating coordinates correctly is half of every matrix problem.

The row-major loop below is the skeleton nearly every matrix algorithm starts from. It visits each cell once, and at each cell it can reach out to the four neighbors.

    graph TD
    S["r = 0, c = 0"] --> L{"r < rows?"}
    L -->|Yes| C{"c < cols?"}
    C -->|Yes| P["Process cell, check neighbors"]
    P --> N["c++"]
    N --> C
    C -->|No| NR["r++, c = 0"]
    NR --> L
    L -->|No| D["Done"]
  

Each cell is processed exactly once because the row and column loops advance in lockstep. The neighbor checks need a bounds test because the edges of the grid have fewer than four neighbors. That bounds test, repeated in every direction, is the part that separates a working matrix solution from one that throws an index error on the first edge case.

The same loop becomes graph search when you add a visited marker and a stack or queue. Flood fill is the DFS version. It claims a cell, then explores the four neighbors. The grid is still a grid, but the route now follows connected regions instead of rows.

When to Use This Pattern

These are the signs that a matrix pattern applies rather than a 1D array trick.

• The input is a 2D array, grid, or board, and every cell has both a row and a column that matter to the answer.
• You need to read or modify cells relative to their neighbors. Boundary checks before every neighbor access are mandatory in that case.
• The problem asks for an in-place transform, like rotating, transposing, or zeroing out entire rows and columns.
• The order of visits is not row-major, like a spiral or diagonal walk. Those orders need explicit boundary tracking.
• The grid represents a graph. Islands, mazes, and game boards all become graph search problems, and grid DFS or BFS is the traversal.

Complexity Analysis

Matrix complexity is stated in terms of M rows and N columns. The product M times N is the number of cells, and most operations visit each cell a constant number of times.

The time is the number of cells in every case because each cell is touched a bounded number of times. The space is constant for traversals that track only boundaries or indices. Grid DFS needs space proportional to the grid when recursion or an explicit stack is used, since the worst case explores the whole grid.

Common Mistakes

These errors all come from the same root: forgetting that a matrix has two indices and edges.

Swapping row and column order. matrix[r][c] is row r, column c. If a problem describes coordinates as (x, y) with x horizontal, the translation to matrix indices is usually (y, x). Getting this backwards turns every up and down move into a left and right move. During practice, trace one “move down” on paper and verify that the row index increased.

Reading neighbors without a bounds check. Writing grid[r + 1][c] directly is safe only when r is not the last row. On the bottom edge this either crashes or reads garbage. The check 0 <= r+1 < rows has to come before the access. Test your solution on a 1-row and a 1-column input and this mistake surfaces immediately.

Off-by-one in spiral traversal. After walking the top row and the right column, the remaining grid may be a single row or a single column. The extra if top <= bottom and if left <= right guards exist for exactly that case. Without them, the left and up passes re-read cells or run past the boundaries. A 1xN or Nx1 input will expose this faster than any test case you invent later.

Zeroing rows while scanning them. If you set the current row and column to zero the moment you see a zero, the later cells in that row look zeroed even though they never were. The standard fix is to record which rows and columns need zeroing in the first row and first column, then apply the changes in a second pass. Dry-run the 2x2 input [[0,1],[1,1]] to see why the recording has to happen before any modification.

Related Patterns

• Graph Traversal . A grid is a graph where each cell is a node and the four neighbors are edges. Grid DFS and BFS reuse the graph traversal machinery, with bounds checks and visited tracking standing in for adjacency lists.
• Array Manipulation . The 1D version of this pattern. Reversal, two pointers, and in-place tricks all carry over to matrices when the second dimension is added.
• Dynamic Programming . Many 2D DP problems build tables where the state is a cell’s coordinates. The matrix pattern handles the table mechanics, and DP handles the recurrence.

Next Steps

Once the concept is clear, the next step is making the code automatic. Check out the code templates for memorizable implementations in 6 languages, then work through the practice problems to apply the pattern to real interview questions.