Pattern #15 — Matrices (2D Grids) 🔲

Pattern #15 — Matrices (2D Grids) 🔲

A matrix is just a grid — rows and columns, like a spreadsheet or a chessboard. This pattern is about the common tricks for moving around and transforming grids.

1. The Basics

   A matrix is an array of arrays:

        col0 col1 col2
   row0 [ 1,   2,   3 ]
   row1 [ 4,   5,   6 ]
   row2 [ 7,   8,   9 ]

   Access an element:  matrix[row][col]
   matrix[1][2] = 6

   Size:  rows = matrix.length,  cols = matrix[0].length

2. Moving in 4 Directions (the #1 tool)

   From a cell (r, c), the 4 neighbours are:

              (r-1, c)   ↑ up
   (r, c-1) ←  (r, c)  → (r, c+1)
        left            right
              (r+1, c)   ↓ down

   The clean way to code this — a "directions" list:

   const dirs = [[-1,0], [1,0], [0,-1], [0,1]];  // up down left right
   for (const [dr, dc] of dirs) {
     const nr = r + dr, nc = c + dc;
     if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
       // valid neighbour (nr, nc)
     }
   }

   💡 This "directions array" trick appears in TONS of grid
      problems (islands, flood fill, shortest path in a maze).

3. 🔍 How to SPOT This Pattern

   Use Matrix techniques when you see:
   ✅ "2D grid", "matrix", "board", "image"
   ✅ "rotate the image", "spiral order", "transpose"
   ✅ "number of islands", "flood fill" (grid + DFS/BFS!)
   ✅ "shortest path in a maze" (grid + BFS!)
   ✅ "search a sorted matrix"

4. Two Classic Transformations

   A) TRANSPOSE — flip across the diagonal (rows ↔ columns)
      [1 2 3]        [1 4 7]
      [4 5 6]   →    [2 5 8]
      [7 8 9]        [3 6 9]
      swap matrix[i][j] with matrix[j][i]

   B) ROTATE 90° CLOCKWISE = transpose, then reverse each row
      [1 2 3]  transpose  [1 4 7]  reverse rows  [7 4 1]
      [4 5 6]     →       [2 5 8]      →         [8 5 2]
      [7 8 9]             [3 6 9]                [9 6 3]

5. The Code Template 📝

   // Rotate an n×n matrix 90° clockwise, in place
   function rotate(matrix) {
     const n = matrix.length;
     // 1. transpose
     for (let i = 0; i < n; i++)
       for (let j = i + 1; j < n; j++)
         [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
     // 2. reverse each row
     for (const row of matrix) row.reverse();
   }

   // Count islands (grid + DFS) — a super common combo
   function numIslands(grid) {
     const rows = grid.length, cols = grid[0].length;
     let count = 0;
     const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
     function sink(r, c) {
       if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0') return;
       grid[r][c] = '0';                     // mark visited
       for (const [dr, dc] of dirs) sink(r + dr, c + dc);
     }
     for (let r = 0; r < rows; r++)
       for (let c = 0; c < cols; c++)
         if (grid[r][c] === '1') { count++; sink(r, c); }
     return count;
   }

6. Practice Problems

   ⭐ core
   • Transpose Matrix
   • Rotate Image
   • Spiral Matrix

   ⭐⭐ Medium
   • Number of Islands (grid + DFS/BFS)
   • Flood Fill
   • Set Matrix Zeroes
   • Search a 2D Matrix
   • Word Search

7. ⚠️ Common Mistake

   ❌ Going out of bounds. ALWAYS check
      0 ≤ row < rows AND 0 ≤ col < cols before accessing a cell.
   ❌ Mixing up [row][col] vs [x][y]. In a grid, the first index
      is usually the ROW (vertical), second is the COLUMN.

Key Takeaway

   Matrices = 2D grids. Master the "directions array" for moving
   to neighbours (up/down/left/right) — it unlocks islands, flood
   fill, and maze problems. Rotate = transpose + reverse rows.
   Always bounds-check.

Next: Pattern #16 — Stacks, the "last in, first out" tool. 📚