🔢 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