Overview#

A 2D array can be thought of as an “array of arrays,” or as a matrix. It uses two dimensions to describe position: rows and columns.

In algorithms, 2D arrays are commonly used for maps, chessboards, image pixels, tables, and dynamic programming state tables. It has one more dimension than a 1D array, and also introduces issues like directions, boundaries, and coordinate transformations.

The key to learning 2D arrays is not memorizing a particular matrix problem, but mastering three models:

• How to traverse every cell;
• How to move in the up, down, left, and right directions;
• How to extend local operations to the entire matrix.

Prerequisites

• Row and column coordinates: 2D arrays locate elements via (row, col)
• Direction arrays: grid search commonly uses four-direction or eight-direction movement
• Boundary checking: every move must confirm the coordinates are valid

Problem Definition#

An m x n matrix can be represented as:

1
matrix[row][col]
2

3
row: 0..m-1
4
col: 0..n-1

For example:

1
[
2
  [1, 2, 3],
3
  [4, 5, 6],
4
  [7, 8, 9]
5
]

Here matrix[1][2] is the element at row 1, column 2, which is 6.

Common 2D array problems can be grouped into several categories:

Core Principles: Step-by-Step Illustration#

1
row = 0: 1 2 3
2
row = 1: 4 5 6
3
row = 2: 7 8 9

1
Up: (-1,  0)
2
Down: ( 1,  0)
3
Left: ( 0, -1)
4
Right: ( 0,  1)

1
nextRow = r + dr
2
nextCol = c + dc

1
old[row][col] -> next[col][n - 1 - row]

Detailed Algorithm Steps#

Taking “Number of Islands” as an example, the search flow for 2D arrays is very typical:

1. Traverse every cell;
2. When encountering land 1, it means a new island has been found;
3. Starting from that cell, use DFS or BFS to mark all connected land;
4. Continue scanning the remaining cells;
5. The final count is the number of islands.

Key boundary checks:

1
0 <= row < rows
2
0 <= col < cols

Whenever you access a 2D array, you should first ask yourself: Is the current position out of bounds? Has it already been visited? Does it satisfy the problem’s conditions?

TypeScript Implementation#

1
function transpose(matrix: number[][]): number[][] {
2
  const rows = matrix.length;
3
  const cols = matrix[0]?.length ?? 0;
4
  const result: number[][] = Array.from({ length: cols }, () => Array(rows));
5

6
  for (let r = 0; r < rows; r++) {
7
    for (let c = 0; c < cols; c++) {
8
      result[c][r] = matrix[r][c];
9
    }
10
  }
11

12
  return result;
13
}

1
function numIslands(grid: string[][]): number {
2
  const rows = grid.length;
3
  const cols = grid[0]?.length ?? 0;
4
  const directions = [
5
    [1, 0],
6
    [-1, 0],
7
    [0, 1],
8
    [0, -1],
9
  ];
10

11
  function dfs(row: number, col: number): void {
12
    if (row < 0 || row >= rows || col < 0 || col >= cols) return;
13
    if (grid[row][col] !== '1') return;
14

15
    grid[row][col] = '0';
16

17
    for (const [dr, dc] of directions) {
18
      dfs(row + dr, col + dc);
19
    }
20
  }
21

22
  let count = 0;
23

24
  for (let row = 0; row < rows; row++) {
25
    for (let col = 0; col < cols; col++) {
26
      if (grid[row][col] === '1') {
27
        count++;
28
        dfs(row, col);
29
      }
30
    }
31
  }
32

33
  return count;
34
}

Engineering Optimization: 2D Prefix Sums#

If you need to frequently query the sum of submatrices, accumulating cell by cell will be very slow. 2D prefix sums can reduce each query to O(1).

1
class NumMatrix {
2
  private readonly prefix: number[][];
3

4
  constructor(matrix: number[][]) {
5
    const rows = matrix.length;
6
    const cols = matrix[0]?.length ?? 0;
7
    this.prefix = Array.from({ length: rows + 1 }, () => Array(cols + 1).fill(0));
8

9
    for (let r = 1; r <= rows; r++) {
10
      for (let c = 1; c <= cols; c++) {
11
        this.prefix[r][c] =
12
          matrix[r - 1][c - 1] +
13
          this.prefix[r - 1][c] +
14
          this.prefix[r][c - 1] -
15
          this.prefix[r - 1][c - 1];
16
      }
17
    }
18
  }
19

20
  sumRegion(row1: number, col1: number, row2: number, col2: number): number {
21
    return (
22
      this.prefix[row2 + 1][col2 + 1] -
23
      this.prefix[row1][col2 + 1] -
24
      this.prefix[row2 + 1][col1] +
25
      this.prefix[row1][col1]
26
    );
27
  }
28
}

Adding one extra row and one extra column as sentinels makes boundary calculations more uniform.

Applications and Limitations#

Summary#

• The core of 2D arrays is row-column coordinates and boundary checking.
• Direction arrays can uniformly handle up, down, left, and right movement.
• Matrix transformations are essentially coordinate mappings.
• Search-type problems are usually traversal + DFS/BFS marking.
• High-frequency region queries are suitable for optimization with 2D prefix sums.