Matrices
Overview
These matrix problems focus on manipulating rows, columns, and rectangular boundaries. The main techniques are transforming a square matrix in place, traversing a matrix layer by layer, reusing part of the matrix as marker storage, and merging sorted rows with a heap.
Carefully define what each index or boundary represents before modifying the matrix. For transformations, map each original coordinate to its destination or decompose the operation into simpler steps such as transposition and reversal. For boundary traversal, shrink top, bottom, left, and right only after their corresponding edge has been processed. When the matrix itself stores state, preserve any information that later steps still need before overwriting cells.
Problems
48. Rotate Image
Rotate an n × n matrix 90 degrees clockwise in place. First flip the matrix vertically by swapping the top and bottom rows, then transpose it across the main diagonal. Together these two transforms produce the required coordinate mapping with O(1) extra space.
class Solution {
public void rotate(int[][] matrix) {
int N = matrix.length;
for (int r = 0; r < N / 2; r++) {
for (int c = 0; c < N; c++) {
int tmp = matrix[r][c];
matrix[r][c] = matrix[N - 1 - r][c];
matrix[N - 1 - r][c] = tmp;
}
}
for (int r = 0; r < N; r++) {
for (int c = 0; c < r; c++) {
int tmp = matrix[r][c];
matrix[r][c] = matrix[c][r];
matrix[c][r] = tmp;
}
}
}
}from typing import List
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
N = len(matrix)
for r in range(N//2):
for c in range(N):
matrix[r][c], matrix[N-1-r][c] = matrix[N-1-r][c], matrix[r][c]
for r in range(N):
for c in range(r):
matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]54. Spiral Matrix
Return matrix values in clockwise spiral order. Keep right and bottom as exclusive boundaries, traverse one edge at a time, and shrink its boundary immediately afterward. After processing the top and right edges, stop if no rows or columns remain so the reverse traversals do not duplicate values.
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int R = matrix.length;
int C = matrix[0].length;
int left = 0;
int right = C;
int top = 0;
int bottom = R;
List<Integer> res = new ArrayList<>();
while (left < right && top < bottom) {
for (int c = left; c < right; c++) {
res.add(matrix[top][c]);
}
top++;
for (int r = top; r < bottom; r++) {
res.add(matrix[r][right - 1]);
}
right--;
if (left == right || top == bottom) {
break;
}
for (int c = right - 1; c >= left; c--) {
res.add(matrix[bottom - 1][c]);
}
bottom--;
for (int r = bottom - 1; r >= top; r--) {
res.add(matrix[r][left]);
}
left++;
}
return res;
}
}from typing import List
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
R, C = len(matrix), len(matrix[0])
left, right = 0, C
top, bottom = 0, R
res = []
while left < right and top < bottom:
for c in range(left, right):
res.append(matrix[top][c])
top += 1
for r in range(top, bottom):
res.append(matrix[r][right-1])
right -= 1
if left == right or top == bottom:
break
for c in range(right-1, left-1, -1):
res.append(matrix[bottom-1][c])
bottom -=1
for r in range(bottom-1, top-1, -1):
res.append(matrix[r][left])
left += 1
return res73. Set Matrix Zeroes
If a cell is zero, clear its entire row and column without allocating marker arrays. Use the first row and first column as marker storage, while row0_zero and col0_zero preserve whether those marker regions must also be cleared.
class Solution {
public void setZeroes(int[][] matrix) {
int R = matrix.length;
int C = matrix[0].length;
boolean row0Zero = false;
boolean col0Zero = false;
for (int c = 0; c < C; c++) {
if (matrix[0][c] == 0) {
row0Zero = true;
break;
}
}
for (int r = 0; r < R; r++) {
if (matrix[r][0] == 0) {
col0Zero = true;
break;
}
}
for (int r = 1; r < R; r++) {
for (int c = 1; c < C; c++) {
if (matrix[r][c] == 0) {
matrix[r][0] = 0;
matrix[0][c] = 0;
}
}
}
for (int r = 1; r < R; r++) {
for (int c = 1; c < C; c++) {
if (matrix[0][c] == 0 || matrix[r][0] == 0) {
matrix[r][c] = 0;
}
}
}
if (row0Zero) {
for (int c = 0; c < C; c++) {
matrix[0][c] = 0;
}
}
if (col0Zero) {
for (int r = 0; r < R; r++) {
matrix[r][0] = 0;
}
}
}
}from typing import List
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
R, C = len(matrix), len(matrix[0])
row0_zero = False
col0_zero = False
for c in range(C):
if matrix[0][c] == 0:
row0_zero = True
break
for r in range(R):
if matrix[r][0] == 0:
col0_zero = True
break
for r in range(1, R):
for c in range(1, C):
if matrix[r][c] == 0:
matrix[r][0] = 0
matrix[0][c] = 0
for r in range(1, R):
for c in range(1, C):
if matrix[0][c] == 0 or matrix[r][0] == 0:
matrix[r][c] = 0
if row0_zero:
for c in range(C):
matrix[0][c] = 0
if col0_zero:
for r in range(R):
matrix[r][0] = 0378. Kth Smallest Element in a Sorted Matrix
Treat each row as a sorted list and merge all rows with a min-heap. Start with the first value from every row. Whenever the smallest value is removed, add the next value from the same row. After removing the first k - 1 values, the heap contains the kth smallest value at its root.
import java.util.PriorityQueue;
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int size = matrix.length;
PriorityQueue<int[]> minHeap = new PriorityQueue<>(
(a, b) -> Integer.compare(a[0], b[0])
);
for (int row = 0; row < size; row++) {
minHeap.offer(new int[] {matrix[row][0], row, 0});
}
while (k - 1 > 0) {
int[] entry = minHeap.poll();
int row = entry[1];
int column = entry[2];
if (column + 1 < size) {
minHeap.offer(new int[] {
matrix[row][column + 1],
row,
column + 1
});
}
k--;
}
return minHeap.peek()[0];
}
}import heapq
from typing import List
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
N = len(matrix)
min_heap = []
for r in range(N):
min_heap.append((matrix[r][0], r, 0)) # value, row, column
heapq.heapify(min_heap)
while k - 1:
num, row, col = heapq.heappop(min_heap)
if col + 1 < N:
heapq.heappush(min_heap, (matrix[row][col + 1], row, col + 1))
k -= 1
return min_heap[0][0]