A matrix is a 2D array organized into rows and columns. In programming, we typically represent it as an array of arrays, where the first index selects the row and the second index selects the column.

The dimensions are typically denoted as m x n where m is the number of rows and n is the number of columns. Be careful with the terminology: rows go horizontally (left to right) and columns go vertically (top to bottom).

In the diagram, the purple cell shows position (1, 2) which contains the value 7. Notice that indices are zero-based: the first row is row 0, and the first column is column 0.

Matrix as an Implicit Graph

The key insight for matrix traversal is that a grid is really just a graph in disguise. Each cell is a node, and adjacent cells (up, down, left, right) are connected by edges. This mental model unlocks all the graph traversal algorithms.

This implicit representation is more memory-efficient than storing an adjacency list, and it allows us to use the grid coordinates directly for indexing.

Direction Arrays: The Key to Grid Navigation

The most important technique for matrix traversal is the direction array. Instead of writing separate logic for moving up, down, left, and right, we encode all directions in arrays and iterate through them.

4-Directional Movement

For problems where you can move up, down, left, and right:

8-Directional Movement

For problems that include diagonal movement:

Using Direction Arrays

Here is how you use direction arrays to explore neighbors:

This pattern appears in almost every matrix traversal problem. Memorize it.

Boundary Checking

One of the most common sources of bugs in matrix problems is going out of bounds. Always check that the new coordinates are valid before accessing the array.

A useful helper method makes your code cleaner and less error-prone:

Matrix Traversal Patterns

There are several ways to traverse a matrix, each useful for different problems.

Linear Traversal

The simplest approach: visit every cell in row-major or column-major order.

Use when: You need to process every cell once, like counting elements or finding a specific value.

Diagonal Traversal

Visit cells along diagonals. Useful for problems involving diagonal patterns.

Spiral Traversal

Visit cells in a spiral pattern, starting from the outer edge and moving inward.

DFS and BFS Traversal

The most powerful patterns for matrix problems. These treat the grid as a graph and explore it using standard graph algorithms.

DFS on Grids

Depth-First Search explores as far as possible along each branch before backtracking. On a grid, this means going in one direction until you hit a boundary or obstacle, then trying another direction.

Recursive DFS Template

Iterative DFS Template (Using Stack)

In-Place Marking

For many problems, instead of using a separate visited array, you can modify the grid itself to mark visited cells. This saves space.

Warning: In-place modification changes the input. Only use this when the problem allows it or when you make a copy first.

BFS on Grids

Breadth-First Search explores all neighbors at the current depth before moving to the next level. On a grid, this means exploring all cells at distance 1, then all cells at distance 2, and so on.

BFS Template

BFS for Shortest Path

BFS naturally finds the shortest path in an unweighted graph. To track the distance, process the queue level by level: