🔢 Matrix

One-line summary: 2D arrays — master spiral traversal, layer-by-layer rotation, and diagonal/anti-diagonal iteration.

---

Concept

Operations: row-by-row, column-by-column, spiral, diagonal, layer rotation, BFS/DFS on grid.

Key trick: matrix[row][col] → after 90° rotation: rotated[col][n-1-row].

---

Time & Space Complexity

Operation	Time	Space
Traverse all cells	O(m·n)	O(1)
Spiral traversal	O(m·n)	O(1)
Rotate in-place	O(n²)	O(1)
BFS/DFS on grid	O(m·n)	O(m·n)

---

Common Patterns

Spiral Order

function spiralOrder(matrix) {
  const result = [];
  let top = 0,
    bottom = matrix.length - 1,
    left = 0,
    right = matrix[0].length - 1;
  while (top <= bottom && left <= right) {
    for (let i = left; i <= right; i++) result.push(matrix[top][i]);
    top++;
    for (let i = top; i <= bottom; i++) result.push(matrix[i][right]);
    right--;
    if (top <= bottom) {
      for (let i = right; i >= left; i--) result.push(matrix[bottom][i]);
      bottom--;
    }
    if (left <= right) {
      for (let i = bottom; i >= top; i--) result.push(matrix[i][left]);
      left++;
    }
  }
  return result;
}

Pascal's Triangle Row

function getRow(rowIndex) {
  const row = new Array(rowIndex + 1).fill(0);
  row[0] = 1;
  for (let i = 1; i <= rowIndex; i++) for (let j = i; j > 0; j--) row[j] += row[j - 1];
  return row;
}

---

Pitfalls

• Spiral: guard top <= bottom and left <= right before reverse passes
• BFS on grid: mark visited immediately when enqueuing, not when dequeuing
• In-place rotation: transpose first, then reverse each row

---

Practice Problems

Problem	Difficulty	Solution
LC 54 — Spiral Matrix	Medium	View Solution
LC 59 — Spiral Matrix II	Medium	View Solution
LC 118 — Pascal's Triangle	Easy	View Solution
LC 119 — Pascal's Triangle II	Easy	View Solution
LC 48 — Rotate Image	Medium
LC 73 — Set Matrix Zeroes	Medium
LC 733 — Flood Fill	Easy
LC 74 — Search a 2D Matrix	Medium
LC 240 — Search a 2D Matrix II	Medium
CC — Matrix Rotation (MTRNSFRM)	Medium
LC 542 — 01 Matrix	Medium
LC 36 — Valid Sudoku	Medium
LC 37 — Sudoku Solver	Hard
LC 79 — Word Search	Medium
LC 130 — Surrounded Regions	Medium
LC 200 — Number of Islands	Medium
LC 212 — Word Search II	Hard
LC 221 — Maximal Square	Medium
LC 289 — Game of Life	Medium
LC 378 — Kth Smallest Element in a Sorted Matrix	Medium
LC 463 — Island Perimeter	Easy
LC 498 — Diagonal Traverse	Medium
LC 695 — Max Area of Island	Medium
LC 766 — Toeplitz Matrix	Easy
LC 867 — Transpose Matrix	Easy
LC 885 — Spiral Matrix III	Medium
LC 994 — Rotting Oranges	Medium
LC 1091 — Shortest Path in Binary Matrix	Medium
LC 1329 — Sort the Matrix Diagonally	Medium
LC 1380 — Lucky Numbers in a Matrix	Easy
LC 1572 — Matrix Diagonal Sum	Easy
LC 1905 — Count Sub Islands	Medium
CC — Matrix Multiplication (MATMUL)	Medium
CC — Grid Paths (GRIDPATH)	Medium
CC — 2D Array Sum (ARRAY2D)	Easy

---

Related Topics

• Two Pointers — converging pointers on matrix rows/columns
• Graphs — BFS/DFS on grid = graph traversal
• Binary Search — 2D sorted matrix search

← Back to Home · © sparshjaswal