# Matrix and 2D Array Traversal Patterns: 8 Essential Techniques for Grid Problems

> Master 8 essential matrix and 2D array traversal patterns like row-major, spiral, and BFS/DFS to conquer grid problems on LeetCode. Optimize your solutions efficiently.

- Repository: [lucifer/leetcode](https://github.com/azl397985856/leetcode)
- Tags: how-to-guide
- Published: 2026-03-06

---

**Row-major, column-major, snake, diagonal, spiral, and graph-based BFS/DFS are the eight fundamental matrix and 2D array traversal patterns used to solve grid-based LeetCode problems.**

A 2-dimensional array, or matrix, is the foundational data structure behind most LeetCode grid problems. Mastering matrix and 2D array traversal patterns is essential for efficiently visiting, reading, and updating cells in specific orders. This guide analyzes concrete implementations found in the `azl397985856/leetcode` repository to provide runnable code examples and authoritative file references.

## Linear Scans: Row-Major and Column-Major Traversal

The most basic matrix and 2D array traversal patterns involve systematic linear scans. These are the default approaches when you need to inspect every element exactly once.

### Row-Major (Left-to-Right, Top-to-Bottom)

**Row-major** traversal processes elements horizontally across each row before moving to the next. This pattern appears in [`problems/73.set-matrix-zeroes.md`](https://github.com/azl397985856/leetcode/blob/main/problems/73.set-matrix-zeroes.md), where the algorithm first scans the entire matrix to identify which rows and columns must be zeroed.

```python
def row_major(matrix):
    rows, cols = len(matrix), len(matrix[0])
    for i in range(rows):
        for j in range(cols):
            # process matrix[i][j]

            print(matrix[i][j], end=' ')
    print()

```

### Column-Major (Top-to-Bottom, Left-to-Right)

**Column-major** traversal inverts the loop order, processing vertically down each column before advancing right. This pattern is essential in [`problems/85.maximal-rectangle.md`](https://github.com/azl397985856/leetcode/blob/main/problems/85.maximal-rectangle.md), which uses column-wise scanning to build histograms for dynamic programming.

## Directional Variations: Snake and Diagonal Patterns

When problems require specific visit orders that deviate from straight lines, directional variations of matrix and 2D array traversal patterns become necessary.

### Snake (Zig-Zag) Traversal

The **snake** pattern alternates direction on each row—left-to-right on even indices, right-to-left on odd indices. This creates a "Z" shaped path useful for board games and specific image scanning algorithms. The logic can be adapted from [`daily/answers/54.spiral-matrix.js`](https://github.com/azl397985856/leetcode/blob/main/daily/answers/54.spiral-matrix.js).

```javascript
function snakeTraverse(mat) {
  const m = mat.length, n = mat[0].length;
  const res = [];
  for (let i = 0; i < m; i++) {
    if (i % 2 === 0) {                 // left → right
      for (let j = 0; j < n; j++) res.push(mat[i][j]);
    } else {                            // right → left
      for (let j = n - 1; j >= 0; j--) res.push(mat[i][j]);
    }
  }
  return res;
}

```

### Diagonal and Anti-Diagonal Traversal

**Diagonal** traversal respects the invariant `i + j = constant`, producing a top-left to bottom-right wave. This is crucial for "Diagonal Traverse" problems and matrix-based DP on diagonals. The [`thinkings/graph.en.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/graph.en.md) file discusses diagonal symmetry in adjacency matrices.

```python
def diagonal_traverse(mat):
    m, n = len(mat), len(mat[0])
    out = []
    for d in range(m + n - 1):
        # elements with i + j == d

        i_start = max(0, d - n + 1)
        i_end   = min(m - 1, d)
        for i in range(i_start, i_end + 1):
            j = d - i
            out.append(mat[i][j])
    return out

```

**Anti-diagonal** traversal starts from the top-right and moves toward the bottom-left, used in [`problems/Longest-Matrix-Path-Length.md`](https://github.com/azl397985856/leetcode/blob/main/problems/Longest-Matrix-Path-Length.md) for specific path-length calculations.

## Layer-Based Traversal: Spiral Order

The **spiral** pattern processes the matrix from the outside in, shrinking boundaries after completing each perimeter. This is the core solution for "Spiral Matrix" and rotation problems. The implementation in [`daily/answers/54.spiral-matrix.js`](https://github.com/azl397985856/leetcode/blob/main/daily/answers/54.spiral-matrix.js) uses four boundary pointers.

```javascript
function spiralOrder(matrix) {
  const res = [];
  if (!matrix.length) return res;
  let top = 0, bottom = matrix.length - 1;
  let left = 0, right = matrix[0].length - 1;

  while (top <= bottom && left <= right) {
    // left → right
    for (let c = left; c <= right; c++) res.push(matrix[top][c]);
    top++;

    // top → bottom
    for (let r = top; r <= bottom; r++) res.push(matrix[r][right]);
    right--;

    if (top <= bottom) {
      // right → left
      for (let c = right; c >= left; c--) res.push(matrix[bottom][c]);
      bottom--;
    }
    if (left <= right) {
      // bottom → top
      for (let r = bottom; r >= top; r--) res.push(matrix[r][left]);
      left++;
    }
  }
  return res;
}

```

## Graph-Based Traversal: BFS and DFS on Grids

Viewing the matrix as an implicit graph—where each cell is a node and edges connect to adjacent cells—enables classic graph algorithms. The [`thinkings/graph.en.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/graph.en.md) file explicitly treats matrices as adjacency matrices, while [`thinkings/binary-tree-traversal.en.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/binary-tree-traversal.en.md) provides the theoretical DFS/BFS foundations applicable to 2-D grids.

### Breadth-First Search (BFS)

**BFS** is optimal for shortest-path problems on unweighted grids, such as flood-fill or multi-source distance calculations.

```python
from collections import deque

def bfs_grid(mat, start):
    m, n = len(mat), len(mat[0])
    q = deque([start])
    visited = [[False] * n for _ in range(m)]
    visited[start[0]][start[1]] = True
    dirs = [(1,0), (-1,0), (0,1), (0,-1)]

    while q:
        r, c = q.popleft()
        # process mat[r][c]

        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc]:
                visited[nr][nc] = True
                q.append((nr, nc))

```

### Depth-First Search (DFS)

**DFS** excels at connected component analysis, such as counting islands or exploring all paths in backtracking puzzles. The recursive neighbor exploration mirrors the DFS concepts detailed in [`thinkings/binary-tree-traversal.en.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/binary-tree-traversal.en.md).

## Advanced: Morris-Style O(1) Space Traversal

For memory-constrained environments, **Morris-style** traversal uses the matrix itself to store temporary pointers, achieving O(1) auxiliary space. While not directly implemented in the repository, the concept is analogous to the Morris traversal discussed in [`thinkings/binary-tree-traversal.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/binary-tree-traversal.md), adapted for 2-D structures.

## Summary

- **Row-major** and **column-major** scans provide the foundation for simple aggregation and dynamic programming over lines.
- **Snake** and **diagonal** patterns alternate directions to satisfy specific ordering constraints like zig-zag or wave traversal.
- **Spiral** traversal uses shrinking boundaries to process matrices from the outside in, essential for rotation and perimeter problems.
- **BFS** and **DFS** treat the grid as a graph, enabling shortest-path calculations and connected component analysis.
- **Morris-style** traversal offers O(1) space complexity for in-place matrix transformations in constrained environments.

## Frequently Asked Questions

### What is the most common matrix and 2D array traversal pattern for LeetCode problems?

**Row-major traversal** is the most frequently encountered pattern because it provides the simplest O(m·n) scan with minimal overhead. It serves as the default approach for counting, summing, and dynamic programming solutions, as demonstrated in [`problems/73.set-matrix-zeroes.md`](https://github.com/azl397985856/leetcode/blob/main/problems/73.set-matrix-zeroes.md).

### How do I choose between BFS and DFS for grid traversal problems?

Choose **BFS** when you need the shortest path on an unweighted grid or require level-order processing, such as in flood-fill or multi-source distance problems. Choose **DFS** when you need to explore all possible paths, count connected components like islands, or solve backtracking puzzles. The [`thinkings/graph.en.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/graph.en.md) file provides the theoretical foundation for both approaches on grids.

### Can spiral matrix traversal be implemented with O(1) extra space?

Yes, **spiral traversal** can be implemented using O(1) auxiliary space by maintaining four boundary pointers (`top`, `bottom`, `left`, `right`) that shrink inward after processing each perimeter. This boundary-shrinking approach avoids creating a separate visited matrix, as shown in [`daily/answers/54.spiral-matrix.js`](https://github.com/azl397985856/leetcode/blob/main/daily/answers/54.spiral-matrix.js).

### Where can I find production-ready implementations of these patterns in the azl397985856/leetcode repository?

The repository contains concrete implementations across several files: [`daily/answers/54.spiral-matrix.js`](https://github.com/azl397985856/leetcode/blob/main/daily/answers/54.spiral-matrix.js) demonstrates spiral and snake logic; [`problems/73.set-matrix-zeroes.md`](https://github.com/azl397985856/leetcode/blob/main/problems/73.set-matrix-zeroes.md) shows row-major scanning; [`problems/85.maximal-rectangle.md`](https://github.com/azl397985856/leetcode/blob/main/problems/85.maximal-rectangle.md) uses column-major traversal; [`problems/Longest-Matrix-Path-Length.md`](https://github.com/azl397985856/leetcode/blob/main/problems/Longest-Matrix-Path-Length.md) implements anti-diagonal navigation; and [`thinkings/graph.en.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/graph.en.md) provides the graph-theoretical foundation for BFS and DFS on grids.