Knowledge Guide
Home › DSA

Matrix

Step 5 in the DSA path · 2 concepts · 7 problems

0 / 9 complete

📘 Learn Matrix from zero

A matrix is a 2-D grid m[r][c]; the pattern is about traversing or transforming it under tight index discipline — managing row/column boundaries, walking in controlled directions, or swapping cells in place. Reach for it whenever the input is a 2-D grid and the answer depends on where a value sits (its row/column/diagonal) rather than just its value. The canonical skill-builder is Spiral Matrix (LeetCode 54): return all elements walking clockwise from the outside in. The trigger to recognize it: "visit every cell in a layered, boundary-shrinking order." We trace it on this 3x4 grid.

✨ Added by the guide to build intuition — not from the source course.

🏗️ Visual walkthrough — trace it step by step

Step 1 — Set the four boundaries
      c=0   1   2   3
      ----------------
r=0 |  1   2   3   4
r=1 |  5   6   7   8
r=2 |  9  10  11  12

top=0  bottom=2  left=0  right=3
result = []

We bound the unvisited region with four walls: top, bottom, left, right. Every layer we walk the top row, right col, bottom row, left col, then shrink one wall inward. This is safe because each cell lives inside exactly one shrinking rectangle and is touched once.

Step 2 — Walk top row left→right
      c=0   1   2   3
r=0 |  1   2   3   4   <= sweep right at row=top(0)
r=1 |  5   6   7   8
r=2 |  9  10  11  12

for c in [left..right]: take m[top][c]
result = [1, 2, 3, 4]
top -> 1   (row 0 now consumed)

Sweep c from left=0 to right=3 along row=top, then do top++. Incrementing top retires row 0 so the next phases never revisit it — that retirement is what guarantees termination.

Step 3 — Walk right column top→bottom
      c=0   1   2   3
r=0 |  .   .   .   .
r=1 |  5   6   7   8|  <= sweep down at col=right(3)
r=2 |  9  10  11  12|
              top=1 bottom=2

for r in [top..bottom]: take m[r][right]
result = [1,2,3,4, 8, 12]
right -> 2   (col 3 now consumed)

Sweep r from top=1 to bottom=2 down col=right=3, taking 8 then 12, then right--. We start at top=1 (not 0) precisely because row 0 was already retired, so 4 is not double-counted.

Step 4 — Walk bottom row right→left
      c=0   1   2
r=1 |  5   6   7
r=2 |  9  10  11   <= sweep left at row=bottom(2)
       <-------
   left=0     right=2

if top<=bottom: for c in [right..left]: take m[bottom][c]
result = [1,2,3,4,8,12, 11, 10, 9]
bottom -> 1   (row 2 now consumed)

Sweep c backward from right=2 to left=0 along row=bottom=2, taking 11, 10, 9, then bottom--. The guard if top<=bottom stops us from re-walking a row in a single-row leftover; here top=1 <= bottom=2 holds, so the sweep is valid.

Step 5 — Walk left column bottom→top
      c=0   1   2
r=1 ||  5   6   7
     ^
  sweep up at col=left(0), r in [bottom..top]
  top=1  bottom=1

if left<=right: for r in [bottom..top]: take m[r][left]
result = [1,2,3,4,8,12,11,10,9, 5]
left -> 1   (col 0 now consumed)

Sweep r upward from bottom=1 to top=1 up col=left=0, taking just 5, then left++. After this the walls are top=1, bottom=1, left=1, right=2 — a 1x2 leftover (cells 6 and 7) still remains. The guard if left<=right protects against a single-column leftover being walked twice.

Step 6 — Last layer: top row of the 1x2 core
      c=1   2
r=1 |  6   7   <= cells left
       ------>
  left=1     right=2

top=1 bottom=1 left=1 right=1... no: left=1 right=2
for c in [left..right]: take m[top][c]
result = [1,2,3,4,8,12,11,10,9,5, 6, 7]
top -> 2   (now top > bottom)

The loop condition top<=bottom and left<=right still holds (1<=1 and 1<=2), so we re-enter. The remaining core is a single row of two cells, so the top-row sweep runs c from left=1 to right=2 and grabs both 6 and 7. Then top++ makes top=2 > bottom=1.

Step 7 — Loop exits, return result
check: top(2) <= bottom(1)?  NO  -> stop

result = [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
count  = 12   (matches the 12 cells of the 3x4 grid)

The walls crossed (top > bottom) right after Step 6 retired the last row, so the loop exits before any redundant phase runs. All 12 cells are present exactly once, with 7 as the final element collected in Step 6's two-cell top-row sweep. Time O(m*n) — each cell visited once; space O(1) beyond output. The four-boundary invariant is the whole trick: shrink a wall right after you consume its line, and you can never revisit or skip a cell.

🎯 Guided practice

  1. Easy — Richest Customer Wealth. Given accounts[m][n] where accounts[i] are one customer's bank balances, return the largest customer total. Reasoning: (1) Each row is one customer, so the "wealth" of customer i is the row sum. (2) Walk rows outer: for each row, sum its columns. (3) Track a running maxWealth = max(maxWealth, rowSum). Trace [[1,2,3],[3,2,1]]: row 0 → 1+2+3=6; row 1 → 3+2+1=6; answer 6. Trace [[1,5],[7,3],[3,5]]: sums 6, 10, 8 → answer 10. Pattern learned: "aggregate per row" is the row-sum loop — O(m*n) time, O(1) space. Recognize it whenever a problem says "per customer / per row / per record."
  2. Easy — Matrix Diagonal Sum. Given an n x n matrix, return the sum of the main diagonal plus the secondary diagonal. Reasoning: (1) The main diagonal is cells where r == c; the secondary (anti-)diagonal is where r + c == n - 1. (2) One linear pass over i from 0 to n-1 adds grid[i][i] and grid[i][n-1-i] — no nested loop needed, so it is O(n) time, O(1) space. (3) Critical edge case: when n is odd the two diagonals share the center cell (n//2, n//2), which you'd count twice — subtract it once. Trace [[1,2,3],[4,5,6],[7,8,9]]: main 1+5+9=15, anti 3+5+7=15, center grid[1][1]=5 double-counted → 15+15-5 = 25. Pattern learned: "index-relationship lookup" — derive which cells matter from a coordinate equation instead of scanning all m*n cells, and always check whether regions overlap on the odd-size center.
  3. Medium — Rotate Image (90° clockwise, in place). Given an n x n matrix, rotate it clockwise without allocating a second grid. Reasoning: The clean trick is transpose, then reverse each row. (1) Transpose = reflect across the main diagonal: swap grid[r][c] with grid[c][r] for every c > r (the c > r guard prevents double-swapping back). (2) Reverse each row in place with two pointers. Trace [[1,2,3],[4,5,6],[7,8,9]]: after transpose → [[1,4,7],[2,5,8],[3,6,9]]; after reversing each row → [[7,4,1],[8,5,2],[9,6,3]], which is the original rotated 90° clockwise. Why it works: a clockwise rotation sends cell (r,c) to position (c, n-1-r); transpose handles the (r,c)→(c,r) index swap and the row-reverse handles the c→n-1-r mirror. Pattern learned: in-place square-matrix transforms decompose into transpose + reflect — O(n²) time, O(1) space — and avoid the off-by-one traps of the alternative four-way layer rotation. Common pitfall: dropping the c > r guard, which transposes twice and leaves the matrix unchanged (verified: a full 0..n double loop returns the original identity).

✨ Added by the guide — work these before the full problem set.

Lessons in this topic