Matrix
Working with 2D Arrays
Matrices, or 2D arrays, are used to represent grids, tables, and images. Interview questions often involve clever traversals and in-place manipulations that test your spatial reasoning.
Representation and Traversal
A matrix with M rows and N columns can be thought of as a grid. Accessing an element is done via two indices: matrix[row][col].
Traversal: A common task is to iterate through every element. This is typically done with nested loops. The standard way this is performed is in row-major order, where the algorithm processes all elements of the first row, then all elements of the second row, and so on. This matches how 2D arrays are often laid out in computer memory, which can have performance benefits due to caching.
# Python for traversing a matrix
rows = len(matrix)
cols = len(matrix[0])
for r in range(rows):
for c in range(cols):
# Do something with matrix[r][c]
pass
Common Matrix Problems & Techniques
1. Spiral Traversal
Problem: Given an m x n matrix, return all elements of the matrix in spiral order.
Approach: Use four pointers to represent the boundaries of the current layer: top, bottom, left, and right. Traverse the top row from left to right, then the right column from top to bottom, then the bottom row from right to left, and finally the left column from bottom to top. After each traversal, shrink the boundaries inwards and repeat until the boundaries cross.
from typing import List
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix:
return []
res = []
left, right = 0, len(matrix[0])
top, bottom = 0, len(matrix)
while left < right and top < bottom:
# Get every i in the top row
for i in range(left, right):
res.append(matrix[top][i])
top += 1
# Get every i in the right col
for i in range(top, bottom):
res.append(matrix[i][right - 1])
right -= 1
if not (left < right and top < bottom):
break
# Get every i in the bottom row (in reverse)
for i in range(right - 1, left - 1, -1):
res.append(matrix[bottom - 1][i])
bottom -= 1
# Get every i in the left col (in reverse)
for i in range(bottom - 1, top - 1, -1):
res.append(matrix[i][left])
left += 1
return res2. Rotate Image
Problem: You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees clockwise. You have to do this in-place.
Approach: A clever two-step process can solve this. First, transpose the matrix (swap matrix[i][j] with matrix[j][i]). Then, reverse each row of the transposed matrix. This results in a 90-degree clockwise rotation.
from typing import List
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
# Transpose matrix
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Reverse each row
for i in range(n):
matrix[i].reverse()3. Set Matrix Zeroes
Problem: Given an m x n integer matrix, if an element is 0, set its entire row and column to 0's. Do this in-place.
Approach: A naive approach using extra O(m+n) space is easy (using two sets to store zeroed rows and columns). To do it in O(1) extra space, we can use the first row and first column of the matrix itself as markers. First, check if the original first row or first column contains any zeroes and store this in boolean variables. Then, iterate through the rest of the matrix (from [1,1]). If matrix[i][j] is 0, set matrix[i][0] = 0 and matrix[0][j] = 0. After marking, iterate through the matrix again and set elements to zero based on the markers in the first row/column. Finally, use the initial boolean variables to handle the first row and column themselves.
from typing import List
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
ROWS, COLS = len(matrix), len(matrix[0])
first_row_zero = False
# Determine which rows/cols need to be zeroed
for r in range(ROWS):
for c in range(COLS):
if matrix[r][c] == 0:
if r == 0:
first_row_zero = True
else:
matrix[r][0] = 0
matrix[0][c] = 0
# Zero out cells based on markers in first row/col
for r in range(1, ROWS):
for c in range(1, COLS):
if matrix[r][0] == 0 or matrix[0][c] == 0:
matrix[r][c] = 0
# Zero out the first row if needed
if matrix[0][0] == 0:
for r in range(ROWS):
matrix[r][0] = 0
# Zero out the first col if needed
if first_row_zero:
for c in range(COLS):
matrix[0][c] = 04. Search in a 2D Sorted Matrix
Problem: The matrix is sorted in two ways: integers in each row are sorted from left to right, and the first integer of each row is greater than the last integer of the previous row.
Approach: Treat the 2D matrix as a single sorted 1D array. You can use binary search directly. The challenge is mapping a 1D index mid back to 2D coordinates: row = mid / N, col = mid % N (where N is the number of columns).
from typing import List
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if not matrix or not matrix[0]:
return False
ROWS, COLS = len(matrix), len(matrix[0])
left, right = 0, ROWS * COLS - 1
while left <= right:
mid_idx = (left + right) // 2
mid_val = matrix[mid_idx // COLS][mid_idx % COLS]
if mid_val == target:
return True
elif mid_val < target:
left = mid_idx + 1
else:
right = mid_idx - 1
return FalseInteractive Demo
Press play on the simulation below to see a row-major traversal in action. The highlighted cell shows the order in which elements are typically accessed by nested loops.
Interactive Matrix Traversal (Row-Major)
Visualize how a computer traverses a 2D array in memory. Row-major order means processing all elements of the first row, then the second, and so on.