🎯 Matrix Problems: Navigating the Grid Like a Pro
Imagine you have a big grid of boxes, like a chocolate bar with squares. Today, we’ll learn how to visit every square, spin the whole bar, and do clever tricks with it!
🌟 The Big Picture
A matrix is like a treasure map made of rows and columns. Each cell holds a value. Learning to navigate matrices is like learning to explore every corner of your favorite game board!
graph TD A["Matrix Problems"] --> B["Traversal Patterns"] A --> C["Spiral Matrix"] A --> D["Rotate Matrix"] A --> E["Set Matrix Zeroes"] A --> F["Search 2D Matrix"]
1️⃣ Matrix Traversal Patterns
What’s the Story?
Think of walking through a classroom. You can:
- Walk row by row (like reading a book, left to right, top to bottom)
- Walk column by column (like going down elevator doors)
- Walk diagonally (like climbing stairs)
Row-Major Traversal
Visit every seat, one row at a time.
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
for row in matrix:
for cell in row:
print(cell, end=' ')
# Output: 1 2 3 4 5 6 7 8 9
Column-Major Traversal
Visit every seat, one column at a time.
rows = len(matrix)
cols = len(matrix[0])
for c in range(cols):
for r in range(rows):
print(matrix[r][c], end=' ')
# Output: 1 4 7 2 5 8 3 6 9
Diagonal Traversal
Walk like you’re going up stairs!
# Main diagonal (top-left to bottom-right)
for i in range(len(matrix)):
print(matrix[i][i], end=' ')
# Output: 1 5 9
💡 Why Does This Matter?
Different problems need different paths. Choosing the right pattern makes solving the problem much easier!
2️⃣ Spiral Matrix
The Story
Imagine an ant walking on a cinnamon roll. It starts from the outside edge and spirals inward until it reaches the yummy center!
→ → → ↓
↑ → ↓ ↓
↑ ↑ ← ↓
↑ ← ← ←
How It Works
We shrink our boundaries as we go:
- Go right along the top row
- Go down the right column
- Go left along the bottom row
- Go up the left column
- Repeat with smaller boundaries!
The Code
def spiral_order(matrix):
result = []
if not matrix:
return result
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
# Go right
for c in range(left, right + 1):
result.append(matrix[top][c])
top += 1
# Go down
for r in range(top, bottom + 1):
result.append(matrix[r][right])
right -= 1
# Go left (if rows remain)
if top <= bottom:
for c in range(right, left - 1, -1):
result.append(matrix[bottom][c])
bottom -= 1
# Go up (if columns remain)
if left <= right:
for r in range(bottom, top - 1, -1):
result.append(matrix[r][left])
left += 1
return result
Example
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
print(spiral_order(matrix))
# Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
3️⃣ Rotate Matrix
The Story
Imagine taking a photo and turning it 90 degrees. Everything moves to a new position, but the picture stays complete!
Before: After (90° clockwise):
1 2 3 7 4 1
4 5 6 → 8 5 2
7 8 9 9 6 3
The Magic Two-Step
Rotating 90° clockwise = Transpose + Reverse each row
Step 1: Transpose (flip along the diagonal)
1 2 3 1 4 7
4 5 6 → 2 5 8
7 8 9 3 6 9
Step 2: Reverse each row
1 4 7 7 4 1
2 5 8 → 8 5 2
3 6 9 9 6 3
The Code
def rotate(matrix):
n = len(matrix)
# Step 1: Transpose
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = \
matrix[j][i], matrix[i][j]
# Step 2: Reverse each row
for row in matrix:
row.reverse()
Example
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
rotate(matrix)
# matrix is now:
# [[7, 4, 1],
# [8, 5, 2],
# [9, 6, 3]]
💡 Pro Tip
For 90° counter-clockwise: Transpose + Reverse each column
4️⃣ Set Matrix Zeroes
The Story
Imagine a game of “hot lava.” If any square has lava (a zero), the entire row and column touching it becomes lava too!
Before: After:
1 1 1 1 0 1
1 0 1 → 0 0 0
1 1 1 1 0 1
The Clever Trick
Instead of using extra space, use the first row and first column as markers!
How It Works
- Check if first row/column originally has zeros
- Use first row/column to mark which rows/columns need zeroing
- Fill zeros based on markers
- Handle first row/column last
The Code
def setZeroes(matrix):
m, n = len(matrix), len(matrix[0])
first_row_zero = False
first_col_zero = False
# Check first row and column
for j in range(n):
if matrix[0][j] == 0:
first_row_zero = True
for i in range(m):
if matrix[i][0] == 0:
first_col_zero = True
# Use first row/col as markers
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# Fill zeros based on markers
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# Handle first row and column
if first_row_zero:
for j in range(n):
matrix[0][j] = 0
if first_col_zero:
for i in range(m):
matrix[i][0] = 0
Example
matrix = [
[0, 1, 2, 0],
[3, 4, 5, 2],
[1, 3, 1, 5]
]
setZeroes(matrix)
# Result:
# [[0, 0, 0, 0],
# [0, 4, 5, 0],
# [0, 3, 1, 0]]
5️⃣ Search a 2D Matrix II
The Story
Imagine a special library where:
- Books on each shelf are sorted left to right
- Books get harder as you go down
You’re looking for a specific book. Start from the top-right corner and play “hot and cold!”
Matrix (sorted rows & columns):
1 4 7 11 15
2 5 8 12 19
3 6 9 16 22
10 13 14 17 24
18 21 23 26 30
Looking for 5? Start at 15!
The Smart Search
From top-right corner:
- If target < current: move left (numbers get smaller)
- If target > current: move down (numbers get bigger)
- If target == current: Found it! 🎉
The Code
def searchMatrix(matrix, target):
if not matrix or not matrix[0]:
return False
rows = len(matrix)
cols = len(matrix[0])
# Start from top-right corner
row = 0
col = cols - 1
while row < rows and col >= 0:
current = matrix[row][col]
if current == target:
return True
elif current > target:
col -= 1 # Move left
else:
row += 1 # Move down
return False
Example Walkthrough
matrix = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22]
]
# Search for 5:
# Start at 15 → 15 > 5 → go left
# At 11 → 11 > 5 → go left
# At 7 → 7 > 5 → go left
# At 4 → 4 < 5 → go down
# At 5 → Found! ✓
print(searchMatrix(matrix, 5)) # True
print(searchMatrix(matrix, 20)) # False
💡 Time Complexity
O(m + n) — Much faster than O(m × n) brute force!
🎯 Quick Summary
| Problem | Key Insight | Time |
|---|---|---|
| Traversal | Choose path based on need | O(m×n) |
| Spiral | Shrink boundaries, 4 directions | O(m×n) |
| Rotate | Transpose + Reverse rows | O(n²) |
| Set Zeroes | Use first row/col as markers | O(m×n) |
| Search 2D | Start top-right, eliminate row/col | O(m+n) |
🚀 You Did It!
You now know how to:
- ✅ Walk through a matrix in any pattern
- ✅ Spiral like a snail into the center
- ✅ Rotate an image without extra space
- ✅ Spread zeros like ripples in a pond
- ✅ Search a sorted matrix super fast
These patterns appear everywhere in coding interviews and real applications. Keep practicing, and these will become second nature!
graph LR A["You"] -->|Learned| B["Matrix Magic"] B --> C["Interview Ready!"] C --> D["🏆 Success!"]