data structures and algorithms
LeetCode: Matrix
10 min read
#data structures and algorithmsMatrix intro
LeetCode problems involving matrixes.
What is a Matrix
Its a grid!
Its got a top, right, bottom, left! What more do you want!??!?! Its a matrix!
48. Rotate Image ::1:: - Medium
Topics: Array, Math, Matrix
Intro
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
| Example Input | Output |
|---|---|
| matrix = [[1,2,3],[4,5,6],[7,8,9]] | [[7,4,1],[8,5,2],[9,6,3]] |
| matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] | [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]] |
Constraints:
n == matrix.length == matrix[i].length
1 ≤ n ≤ 20
-1000 ≤ matrix[i][j] ≤ 1000
Abstraction
Given an 2D array, rotate the 2D array 90 degrees.
Pseudocode
text will go here
Solution 1: Layer by Layer Rotation - Math and Geometry/Math and Geometry
def rotate(self, matrix: List[List[int]]) -> None:
# Note:
# Rotate n x n matrix 90 degrees clockwise in place
# 1. Process the matrix layer by layer (outermost to innermost)
# 2. For each layer, rotate elements in four way swaps:
# Top -> Right -> Bottom -> Left -> Top
# 3. Repeat for all layers
# Result -> No extra matrix allocation, in place modification
# Example (n=3, outer layer rotation):
# [1, 2, 3] [7, 4, 1]
# [4, 5, 6] ---> [8, 5, 2]
# [7, 8, 9] [9, 6, 3]
n = len(matrix)
# There are n//2 layers
# Odd sized matrix -> one single center cell, inner does not rotate
# Even sized matrix -> no single center cell, all layers rotate
layers = n//2
for layer in range(layers):
# first -> start index of current ring (top-left corner)
first = layer
# last -> end index of current ring (bottom-right corner)
# layer 1:
# [ 1, 1, 1, 1, 1, 1]
# [ 1, 1, 1, 1, 1, 1]
# f^. l^
# ...
# ...
last = n - 1 - layer
# length of current ring - 1
# notice we only need 3 swaps as 4th swap is 1 swap of next switch
# [1, 2, 3, 4 ]
# [5, 6, 7, 8 ]
# [9, 10, 11, 12]
# [13, 14, 15, 16]
# we only swap, 1, 2, 3, as 4 will be taken care of
# by the next iteration, therefore ringLen is -1 its actual length
# thus ring len of 4 goes to 3
ringLen = last - first
# iterate -> 0 to ringLen-1
for i in range(ringLen):
# left -> top
# bottom -> left
# right -> bottom
# saved top -> right
# save top
top_val = matrix[first][first + i]
# top: left right via row || left: bottom up via column
matrix[first][first + i] = matrix[last - i][first]
# left: bottom up via column || bottom: right left via row
matrix[last - i][first] = matrix[last][last - i]
# bottom: right left via row || right: top down via column
matrix[last][last - i] = matrix[first + i][last]
# right: top down via column || top: left right via row
matrix[first + i][last] = top_val
# overall: time complexity O(n^2)
# overall: space complexity O(1)Solution 2: Transpose And Reverse - Math and Geometry/Math and Geometry
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
# -----------------------------
# Step 1: Transpose the matrix
# Swap elements across the main diagonal
# matrix[i][j] <-> matrix[j][i]
# Only swap for j > i to avoid double swap
# -----------------------------
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
# Reversing rows after transpose achieves 90° clockwise rotation
# -----------------------------
for i in range(n):
matrix[i].reverse()
# overall: time complexity O(n^2)
# overall: space complexity O(1) in-place73. Set Matrix Zeroes ::1:: - Medium
Topics: Array, Hash Table, Matrix
Intro
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's. You must do it in place. Follow up: A straightforward solution using O(mn) space is probably a bad idea. A simple improvement uses O(m + n) space, but still not the best solution. Could you devise a constant space solution?
| Example Input | Output |
|---|---|
| matrix = [[1,1,1],[1,0,1],[1,1,1]] | [[1,0,1],[0,0,0],[1,0,1]] |
| matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] | [[0,0,0,0],[0,4,5,0],[0,3,1,0]] |
Constraints:
m == matrix.length
n == matrix[i].length
1 ≤ m, n ≤ 200
-231 ≤ matrix[i][j] ≤ 231 - 1
Abstraction
Given a 2D array, if a cell has 0, zero out its adjacent row and column.
Pseudocode
text will go here
Solution 1: Brute Force O(m*n) Space - Math and Geometry/Math and Geometry
def setZeroes(self, matrix: List[List[int]]) -> None:
# Note:
# Separate iterating from writing via creating copy of matrix using O(m*n)
# We read over the copy while updating the original in place
# 1. Iterate through original matrix
# 2. If cell is 0, set corresponding row and column in copy to 0
# 3. Copy back to original matrix
# Result -> original matrix set correctly in place
m, n = len(matrix), len(matrix[0])
# Create a copy
copy = [row[:] for row in matrix] # O(m*n) space
for i in range(m):
for j in range(n):
if copy[i][j] == 0:
# Zero entire row
for col in range(n):
matrix[i][col] = 0
# Zero entire column
for row in range(m):
matrix[row][j] = 0
# overall: time complexity O(m*n*(m+n)) due to nested zeroing loops
# overall: space complexity O(m*n) for copySolution 2: Using O(m+n) Space - Math and Geometry/Math and Geometry
def setZeroes(self, matrix: List[List[int]]) -> None:
# Note:
# Separate iterating from writing via creating copy of matrix using O(m+n)
# Use two arrays to store flags to track zero rows and zero columns
# 1. row_flag[m] -> True if row i should be zero
# 2. col_flag[n] -> True if column j should be zero
# 3. Iterate matrix, set flags
# 4. Iterate matrix again, zero out flagged rows and columns
# Result -> original matrix set correctly in place
m, n = len(matrix), len(matrix[0])
row_flag = [False] * m
col_flag = [False] * n
# Flag zero rows and columns
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
row_flag[i] = True
col_flag[j] = True
# Zero out flagged rows and columns in original matrix
for i in range(m):
for j in range(n):
if row_flag[i] or col_flag[j]:
matrix[i][j] = 0
# overall: time complexity O(m*n)
# overall: space complexity O(m+n)Solution 3: Constant Space O(1) - Math and Geometry/Math and Geometry
def setZeroes(self, matrix: List[List[int]]) -> None:
# Note:
# Separate iterating from writing via creating copy of matrix using O(m+n)
# We use the first row and first column of the matrix itself
# 1. row_flag[m] -> True if row i should be zero
# 2. col_flag[n] -> True if column j should be zero
# 4. Iterate matrix again, zero out flagged rows and columns
# Result -> original matrix set correctly in place
# Boundaries
m, n = len(matrix), len(matrix[0])
# Pre check if first row has any zeros
first_row_zero = False
for j in range(n):
if matrix[0][j] == 0:
first_row_zero = True
break
# Pre check if first column has any zeros
first_col_zero = False
for i in range(m):
if matrix[i][0] == 0:
first_col_zero = True
break
# Set zero flags using first row and column
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0 # mark row
matrix[0][j] = 0 # mark column
# Using zero flags, zero out rows and cols
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
# Afterwards:
# Zero out the first row if needed
if first_row_zero:
for j in range(n):
matrix[0][j] = 0
# Afterwards:
# Zero out the first column if needed
if first_col_zero:
for i in range(m):
matrix[i][0] = 0
# overall: time complexity O(m*n)
# overall: space complexity O(1)54. Spiral Matrix ::1:: - Medium
Topics: Array, Matrix, Simulation
Intro
Given an m x n matrix, return all elements of the matrix in spiral order.
| Example Input | Output |
|---|---|
| matrix = [[1,2,3],[4,5,6],[7,8,9]] | [1,2,3,6,9,8,7,4,5] |
| matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] | [1,2,3,4,8,12,11,10,9,5,6,7] |
Constraints:
m == matrix.length
n == matrix[i].length
1 ≤ m, n ≤ 10
-100 ≤ matrix[i][j] ≤ 100
Abstraction
Given a 2D array, return a list of all the elements in the matrix by iterating in a clockwise rotation.
Pseudocode
text will go here
Solution 1: Layer by Layer Spiral Traversal - Math and Geometry/Math and Geometry
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
# Note:
# Traverse the matrix in clockwise spiral order using layers
# 1. Treat each layer as a shrinking “frame” around the matrix
# 2. For each layer, traverse top row, right column, bottom row, left column
# 3. Increment layer and repeat until all elements are processed
# Empty check
if not matrix or not matrix[0]:
return []
res = []
# boundaries
m, n = len(matrix), len(matrix[0])
# number of layer -> min between rows and columns
# There are (min(row, col) // 2) layers
# Odd sized matrix -> one single center cell
# Even sized matrix -> no single center cell
layers = (min(m, n) + 1) // 2
for layer in range(layers):
# boundaries of current layer
first_row = layer
first_col = layer
# inclusive via last element
# layer 1:
# [ 1, 1, 1, 1, 1, 1]
# [ 1, 1, 1, 1, 1, 1]
# f^. l^
# ...
# ...
last_row = m - 1 - layer
last_col = n - 1 - layer
# Top and Right sides always exist in every layer
# Bottom and left may not always exist
# Top row: left -> right
for col in range(first_col, last_col + 1):
res.append(matrix[first_row][col])
# Right column: top+1 -> bottom
for row in range(first_row + 1, last_row + 1):
res.append(matrix[row][last_col])
# Bottom row: right-1 -> left (if more than one row)
if last_row > first_row:
for col in range(last_col - 1, first_col - 1, -1):
res.append(matrix[last_row][col])
# Left column: bottom-1 -> top+1 (if more than one column)
if last_col > first_col:
for row in range(last_row - 1, first_row, -1):
res.append(matrix[row][first_col])
# overall: time complexity O(m*n)
# overall: space complexity O(m*n) for output list
return res