1.3 Matrix

Deep Dive: See the Geometry

Beginner tip: A matrix is just a grid of numbers, like a spreadsheet. You access cells by row and column: matrix[row][col]. Matrix problems test whether you can think in 2D -- moving, rotating, and searching through grids.

Rotate 90 Degrees -- Why Transpose + Reverse Works

Original, then transpose (swap rows/cols), then reverse each row:

Original:       Transpose:      Reverse rows:
1 2 3           1 4 7           7 4 1
4 5 6    ->     2 5 8    ->     8 5 2
7 8 9           3 6 9           9 6 3

Verify: top-left 1 moved to top-right. Top-right 3 moved to bottom-right. That is 90-degree clockwise rotation. Two simple operations, no complex index math.

Spiral Matrix -- Layer by Layer

Layer 0 (outermost):
 1 -> 2 -> 3
             |
12   ...    4
 |           |
11          5
 |           |
10 <- 9 <- 8
             
top=0, bottom=3, left=0, right=3
Right: row=0, col 0->3   then top++
Down:  col=3, row 1->3   then right--
Left:  row=3, col 2->0   then bottom--
Up:    col=0, row 2->1   then left++

Layer 1 (inner):
same logic with updated boundaries

Set Matrix Zeroes -- The Marker Trick

Problem: if a cell is 0, zero out its entire row and column. But if you zero immediately, you corrupt other cells.

Step 1: Use first row and first col AS markers:
        If matrix[r][c]==0, set matrix[r][0]=0 and matrix[0][c]=0

Step 2: Zero interior cells based on markers (row 1+, col 1+)

Step 3: Handle first row and first col separately
        (since they were used as markers, process them last)

This avoids O(m+n) extra space for tracking which rows/cols to zero.

---

Quick Reference (Cheat Sheet)

Before You Start -- How to Think About Matrix Problems

Why Matrix Is Its Own Category

Matrix problems test spatial reasoning--how you traverse, rotate, and modify a 2D grid in place. They're a FAANG favorite because they feel different from 1D arrays even though the techniques overlap.

Mental Models

ROTATE 90 degrees CLOCKWISE:
  Step 1: Transpose (swap rows and columns: matrix[i][j] <-> matrix[j][i])
  Step 2: Reverse each row
  That's it. Don't try to rotate directly -- it's error-prone.

SPIRAL TRAVERSAL:
  Process layer by layer: top row -> right column -> bottom row -> left column
  Shrink the boundaries after each layer.

FLOOD FILL / ISLAND COUNTING:
  DFS or BFS from each unvisited cell. Mark visited as you go.

IN-PLACE MARKING (Set Matrix Zeroes):
  Use first row and first column as markers instead of extra O(mxn) space.

When You See a Matrix Problem, Ask Yourself

1. Is this a TRAVERSAL problem? -> DFS / BFS on grid
2. Is this a ROTATION / TRANSFORMATION? -> Transpose trick or layer-by-layer
3. Do I need to MARK cells? -> Can I use the matrix itself as storage?
4. Is this a SEARCH in sorted matrix? -> Staircase search (top-right corner)

Common Mistakes

• Modifying the matrix while iterating (use copy or in-place markers)
• Forgetting to check grid boundaries in DFS/BFS: 0 <= r < rows and 0 <= c < cols
• Confusing rows/columns: matrix[row][col], not matrix[x][y]

Problems

#	Problem	Difficulty	Pattern	Status
1	Set Matrix Zeroes	Medium	In-place marking	[ ]
2	Spiral Matrix	Medium	Layer-by-layer	[ ]
3	Rotate Image	Medium	Transpose + Reverse	[ ]
4	Word Search	Medium	Grid DFS	[ ]
5	Search a 2D Matrix	Medium	Binary Search	[ ]

Notes