🤔 Why Master Matrix Algorithms?
🖼️ Image Processing
Every image is a matrix of pixels. Filters, rotations, and effects are matrix operations!
🎮 Game Development
Game boards, pathfinding (A*), collision detection - all use 2D grids and matrices.
📊 Data Science
Machine learning features, correlation matrices, and data transformations.
🗺️ Maps & Navigation
GPS systems use grid-based algorithms to find shortest paths and optimal routes.
💡 Think of Matrices as Spreadsheets!
A matrix is just like an Excel spreadsheet - rows and columns of data that you can navigate and manipulate.
🌟 Matrix Fundamentals
Understanding 2D Arrays - Think of a Chess Board! ♟️
0,0
0,1
0,2
0,3
1,0
1,1
1,2
1,3
2,0
2,1
2,2
2,3
Each cell has two coordinates: [row][column], just like (x,y) in math!
Creating and Accessing Matrices 📊
# Creating a matrix (2D array) in Python
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
# Accessing elements
element = matrix[1][2] # Gets 6 (row 1, column 2)
# Getting dimensions
rows = len(matrix) # Number of rows
cols = len(matrix[0]) # Number of columns
# Creating an empty matrix of specific size
def create_matrix(rows, cols, default=0):
return [[default for _ in range(cols)] for _ in range(rows)]
# Create 3x4 matrix filled with zeros
empty_matrix = create_matrix(3, 4)
Safe Matrix Access 🛡️
def is_valid(matrix, row, col):
"""Check if position is within matrix bounds"""
return (0 <= row < len(matrix) and
0 <= col < len(matrix[0]))
def safe_access(matrix, row, col, default=None):
"""Safely access matrix element"""
if is_valid(matrix, row, col):
return matrix[row][col]
return default
# Directions for neighbors (up, right, down, left)
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
def get_neighbors(matrix, row, col):
"""Get all valid neighbors of a cell"""
neighbors = []
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
if is_valid(matrix, new_row, new_col):
neighbors.append((new_row, new_col))
return neighbors
🔄 Matrix Traversal Patterns
Row-by-Row Traversal 📖
def traverse_row_by_row(matrix):
"""Read matrix like a book - left to right, top to bottom"""
result = []
for row in range(len(matrix)):
for col in range(len(matrix[0])):
result.append(matrix[row][col])
return result
# Example: [[1,2,3],[4,5,6]] → [1,2,3,4,5,6]
Spiral Traversal 🌀
def spiral_order(matrix):
"""Traverse matrix in spiral order - like peeling an onion!"""
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 along top row
for col in range(left, right + 1):
result.append(matrix[top][col])
top += 1
# Go down along right column
for row in range(top, bottom + 1):
result.append(matrix[row][right])
right -= 1
# Go left along bottom row (if we have rows left)
if top <= bottom:
for col in range(right, left - 1, -1):
result.append(matrix[bottom][col])
bottom -= 1
# Go up along left column (if we have columns left)
if left <= right:
for row in range(bottom, top - 1, -1):
result.append(matrix[row][left])
left += 1
return result
Diagonal Traversal ↗️
def diagonal_traverse(matrix):
"""Traverse matrix diagonally (zigzag pattern)"""
if not matrix:
return []
rows, cols = len(matrix), len(matrix[0])
result = []
# Process all diagonals
for d in range(rows + cols - 1):
diagonal = []
# Find starting point of diagonal
if d < cols:
row, col = 0, d
else:
row, col = d - cols + 1, cols - 1
# Collect diagonal elements
while row < rows and col >= 0:
diagonal.append(matrix[row][col])
row += 1
col -= 1
# Reverse every other diagonal for zigzag
if d % 2 == 0:
diagonal.reverse()
result.extend(diagonal)
return result
⚙️ Matrix Operations
Matrix Rotation 🔄
def rotate_90_clockwise(matrix):
"""Rotate matrix 90 degrees clockwise
Trick: Transpose + Reverse each row
"""
n = len(matrix)
# Step 1: Transpose (swap row and column indices)
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Step 2: Reverse each row
for row in matrix:
row.reverse()
return matrix
def rotate_90_counter_clockwise(matrix):
"""Rotate matrix 90 degrees counter-clockwise
Trick: Reverse each row + Transpose
"""
n = len(matrix)
# Step 1: Reverse each row
for row in matrix:
row.reverse()
# Step 2: Transpose
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
return matrix
Matrix Search 🔍
def search_in_sorted_matrix(matrix, target):
"""Search in row-wise and column-wise sorted matrix
Start from top-right or bottom-left corner!
"""
if not matrix:
return False
rows, cols = len(matrix), len(matrix[0])
# Start from top-right corner
row, col = 0, cols - 1
while row < rows and col >= 0:
if matrix[row][col] == target:
return True
elif matrix[row][col] > target:
col -= 1 # Move left
else:
row += 1 # Move down
return False
# Example: Search in sorted matrix
matrix = [
[1, 4, 7, 11],
[2, 5, 8, 12],
[3, 6, 9, 16]
]
# search_in_sorted_matrix(matrix, 5) → True
🚀 Advanced Matrix Algorithms
Island Counting (DFS) 🏝️
def count_islands(grid):
"""Count number of islands (connected 1s) in binary matrix"""
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
islands = 0
def dfs(row, col):
"""Mark all connected land as visited"""
if (row < 0 or row >= rows or
col < 0 or col >= cols or
grid[row][col] != 1):
return
grid[row][col] = -1 # Mark as visited
# Explore all 4 directions
dfs(row + 1, col)
dfs(row - 1, col)
dfs(row, col + 1)
dfs(row, col - 1)
# Find and count all islands
for row in range(rows):
for col in range(cols):
if grid[row][col] == 1:
islands += 1
dfs(row, col)
return islands
Dynamic Programming on Grid 💎
def min_path_sum(grid):
"""Find minimum path sum from top-left to bottom-right
Can only move right or down
"""
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
# Initialize first row
for col in range(1, cols):
grid[0][col] += grid[0][col - 1]
# Initialize first column
for row in range(1, rows):
grid[row][0] += grid[row - 1][0]
# Fill rest of the grid
for row in range(1, rows):
for col in range(1, cols):
grid[row][col] += min(grid[row - 1][col],
grid[row][col - 1])
return grid[rows - 1][cols - 1]
def unique_paths(m, n):
"""Count unique paths in m×n grid
Mathematical solution: (m+n-2)! / ((m-1)! * (n-1)!)
"""
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
⚠️ Common Matrix Pitfalls
- Index confusion: Remember [row][col], not [x][y]
- Boundary checking: Always validate indices
- Modifying while traversing: Can cause infinite loops
- Space complexity: Creating copies vs in-place operations
💪 Practice Problems
🟢 Easy: Transpose Matrix
▼
Problem: Convert rows to columns and columns to rows.
Example: [[1,2,3],[4,5,6]] → [[1,4],[2,5],[3,6]]
def transpose(matrix):
"""Transpose a matrix (swap rows and columns)"""
rows, cols = len(matrix), len(matrix[0])
# Create new matrix with swapped dimensions
result = [[0] * rows for _ in range(cols)]
for i in range(rows):
for j in range(cols):
result[j][i] = matrix[i][j]
return result
🟡 Medium: Set Matrix Zeroes
▼
Problem: If element is 0, set entire row and column to 0.
Challenge: Do it in-place with O(1) extra space.
def set_zeroes(matrix):
"""Set entire row and column to 0 if element is 0"""
rows, cols = len(matrix), len(matrix[0])
first_row_zero = False
first_col_zero = False
# Check if first row/col have zeros
for j in range(cols):
if matrix[0][j] == 0:
first_row_zero = True
break
for i in range(rows):
if matrix[i][0] == 0:
first_col_zero = True
break
# Use first row/col as markers
for i in range(1, rows):
for j in range(1, cols):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# Set zeros based on markers
for i in range(1, rows):
for j in range(1, cols):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# Handle first row/col
if first_row_zero:
for j in range(cols):
matrix[0][j] = 0
if first_col_zero:
for i in range(rows):
matrix[i][0] = 0
🔴 Hard: Word Search in Grid
▼
Problem: Find if word exists in grid (can move in 4 directions).
Technique: Backtracking with DFS.
def exist(board, word):
"""Search for word in matrix using DFS + backtracking"""
if not board:
return False
rows, cols = len(board), len(board[0])
def dfs(row, col, index):
if index == len(word):
return True
if (row < 0 or row >= rows or
col < 0 or col >= cols or
board[row][col] != word[index]):
return False
# Mark as visited
temp = board[row][col]
board[row][col] = '#'
# Explore all 4 directions
found = (dfs(row + 1, col, index + 1) or
dfs(row - 1, col, index + 1) or
dfs(row, col + 1, index + 1) or
dfs(row, col - 1, index + 1))
# Backtrack
board[row][col] = temp
return found
# Try starting from each cell
for i in range(rows):
for j in range(cols):
if dfs(i, j, 0):
return True
return False
🎯 Matrix Mastery Checklist
- ✅ Can create and access 2D arrays
- ✅ Know common traversal patterns
- ✅ Can rotate and transform matrices
- ✅ Understand DFS/BFS on grids
- ✅ Can apply DP to grid problems