All Roadmaps›🧠 Data Structures & Algorithms›Phase 2›Matrices & 2D Arrays

Matrices & 2D Arrays

0/14 in this phase0/57 across the roadmap

📖 Concept

A matrix (2D array) is an array of arrays — representing grids, tables, images, game boards, and graph adjacency.

Key concepts:

  • Access: matrix[row][col] — O(1)
  • Dimensions: rows = matrix.length, cols = matrix[0].length
  • Total elements: rows × cols

Common matrix patterns in interviews:

  1. Traversal: Row-wise, column-wise, diagonal, spiral
  2. Search: Binary search in sorted matrix
  3. DFS/BFS: Island counting, flood fill, shortest path in grid
  4. In-place modification: Rotate 90°, set zeroes
  5. Dynamic programming: Grid paths, minimum path sum

Direction arrays (essential for grid problems):

// 4 directions: up, down, left, right
const dirs = [[-1,0], [1,0], [0,-1], [0,1]];
// 8 directions: include diagonals
const dirs8 = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];

🏠 Real-world analogy: A spreadsheet is a 2D array — rows and columns with data at each cell. Image processing works on 2D pixel matrices. Game boards (chess, sudoku) are 2D grids.

💻 Code Example

codeTap to expand ⛶
1// CREATE AND TRAVERSE A MATRIX
2const matrix = [
3  [1, 2, 3],
4  [4, 5, 6],
5  [7, 8, 9]
6];
7

8// Row-wise traversal
9for (let r = 0; r < matrix.length; r++) {
10  for (let c = 0; c < matrix[0].length; c++) {
11    console.log(matrix[r][c]);
12  }
13}
14

15// SPIRAL ORDER TRAVERSAL
16function spiralOrder(matrix: number[][]): number[] {
17  const result: number[] = [];
18  let top = 0, bottom = matrix.length - 1;
19  let left = 0, right = matrix[0].length - 1;
20

21  while (top <= bottom && left <= right) {
22    for (let i = left; i <= right; i++) result.push(matrix[top][i]);
23    top++;
24    for (let i = top; i <= bottom; i++) result.push(matrix[i][right]);
25    right--;
26    if (top <= bottom) {
27      for (let i = right; i >= left; i--) result.push(matrix[bottom][i]);
28      bottom--;
29    }
30    if (left <= right) {
31      for (let i = bottom; i >= top; i--) result.push(matrix[i][left]);
32      left++;
33    }
34  }
35  return result;
36}
37

38// ROTATE MATRIX 90° CLOCKWISE — In-place O(1) space
39function rotate(matrix: number[][]): void {
40  const n = matrix.length;
41  // Step 1: Transpose (swap rows and columns)
42  for (let i = 0; i < n; i++) {
43    for (let j = i + 1; j < n; j++) {
44      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
45    }
46  }
47  // Step 2: Reverse each row
48  for (const row of matrix) row.reverse();
49}
50

51// COUNT ISLANDS — Grid DFS
52function numIslands(grid: string[][]): number {
53  let count = 0;
54  const rows = grid.length, cols = grid[0].length;
55  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
56

57  function dfs(r: number, c: number): void {
58    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') return;
59    grid[r][c] = '0'; // Mark visited
60    for (const [dr, dc] of dirs) dfs(r + dr, c + dc);
61  }
62

63  for (let r = 0; r < rows; r++) {
64    for (let c = 0; c < cols; c++) {
65      if (grid[r][c] === '1') { count++; dfs(r, c); }
66    }
67  }
68  return count;
69}
70

71// SEARCH IN SORTED MATRIX — O(m + n)
72function searchMatrix(matrix: number[][], target: number): boolean {
73  let row = 0, col = matrix[0].length - 1; // Start top-right
74  while (row < matrix.length && col >= 0) {
75    if (matrix[row][col] === target) return true;
76    if (matrix[row][col] > target) col--;
77    else row++;
78  }
79  return false;
80}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

  1. Traverse a matrix in spiral order
  2. Rotate a matrix 90 degrees clockwise in-place
  3. Set entire row and column to 0 if any element is 0
  4. Count the number of islands in a grid (connected 1s)
  5. Search for a target in a row-wise and column-wise sorted matrix
  6. Find the shortest path in a binary maze (BFS)
  7. Word search — find if a word exists in a grid (backtracking)
  8. Flood fill (paint bucket tool in image editors)
  9. Maximum sum rectangle in a 2D matrix
  10. Compute the diagonal sum of a matrix

⚠️ Common Mistakes

  • Confusing row and column indices — matrix[row][col], not matrix[x][y]

  • Not checking bounds before accessing neighbors — always verify r >= 0, r < rows, c >= 0, c < cols

  • Forgetting to mark visited cells in grid DFS/BFS — leads to infinite loops

  • Modifying the input grid when the problem doesn't allow it — use a visited set instead

  • Creating a matrix with shared row references — new Array(3).fill(new Array(3).fill(0)) shares the SAME inner array

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Matrices & 2D Arrays

← PreviousRecursion-Based Structures (Linked List Ops, Nested Structures)Next →Sorting Algorithms (Bubble, Selection, Insertion, Merge, Quick)