CMD Guide
Home › DSA

Matrix

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

0 / 8 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

🧠 Review & recall

Active recall is what moves a topic into long-term memory. Flip each card before revealing, then test yourself — your results are saved on this device.

Flashcard
When should you reach for the Matrix pattern, and what is its defining discipline?
tap to reveal →
Reach for it whenever the input is a 2-D grid m[r][c] and the answer depends on where a value sits (its row, column, or diagonal) rather than just its value. The pattern is about index discipline: managing row/column boundaries, walking in controlled directions, or swapping cells in place.
💡 2-D grid + position matters = matrix discipline.
Flashcard
What is the four-boundary technique for Spiral Matrix, and why does it never revisit or skip a cell?
tap to reveal →
Maintain top, bottom, left, right walls. While top<=bottom and left<=right, walk the top row left→right (top++), right col top→bottom (right--), bottom row right→left (bottom--), then left col bottom→top (left++). Shrinking a wall right after consuming its line means each cell lives in exactly one shrinking rectangle, so it is touched once. Time O(m*n), space O(1) beyond output.
💡 Shrink the wall the instant you consume its line.
Flashcard
Why do the bottom-row and left-column sweeps in Spiral Matrix need 'if top<=bottom' and 'if left<=right' guards?
tap to reveal →
After the top row and right column are retired, a single leftover row or single leftover column could be walked a second time. The guard 'if top<=bottom' protects a single-row leftover from being re-walked by the bottom sweep, and 'if left<=right' protects a single-column leftover from the left sweep.
💡 Guards stop the lone leftover row/column from a double-walk.
Flashcard
How do you rotate an n x n matrix 90° clockwise in place, and what coordinate move does it implement?
tap to reveal →
Transpose (swap matrix[i][j] with matrix[j][i] for j from i to n-1), then reverse each row (swap [i][j] with [i][n-1-j] for j up to n/2). A clockwise rotation sends cell (r,c) to (c, n-1-r): transpose does the (r,c)→(c,r) swap and the row-reverse does the c→n-1-r mirror. O(n²) time, O(1) space.
💡 Transpose, then reverse each row = clockwise.
Flashcard
For Matrix Diagonal Sum, which index relations pick the two diagonals, and what is the critical edge case?
tap to reveal →
The primary diagonal is cells where row==col (mat[i][i]); the secondary diagonal is where col = n-1-i (mat[i][n-1-i]). Add both in one O(n) pass. Critical: when n is odd the center cell mat[n/2][n/2] lies on both diagonals and gets counted twice, so subtract it once. O(n) time, O(1) space.
💡 Odd n? The center is double-counted — subtract it once.
Flashcard
How does Set Matrix Zeroes achieve O(1) extra space, and what extra flag is needed?
tap to reveal →
Use the matrix's own first row and first column as markers: on the first pass, for each zero at (i,j) set matrix[0][j] and matrix[i][0] to zero; on the second pass, zero any cell whose row-marker or column-marker is zero. Because the first column's markers overlap with column-0 zeros, keep a separate boolean isCol to remember if the first column itself must be zeroed, and handle the first row/column last.
💡 First row + first column are the marker board; isCol covers the overlap.
Q1. In Valid Sudoku, how is the 3x3 sub-box index computed for the cell at row i, column j?
Q2. For Spiral Matrix on [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], what is the spiral-order output?
Q3. Rotating [[5,1,9],[2,4,8],[13,3,6]] 90° clockwise in place via transpose-then-reverse-rows gives what result?
Q4. Why does Matrix Diagonal Sum subtract mat[n/2][n/2] only when n is odd?
Q5. In Row With Maximum Ones, when two rows tie for the most ones, which is returned and why?