Matrices

Matrix problems are quite common and are relatively straightforward, just focus on understanding the techniques required

Runtime analysis

Most matrix problems have a run time of O(mn)O(mn)for a mƗnm \times nmatrix

Corner cases

  • Empty matrix (ensure none of the array length is 0)

  • 1 by 1 matrix

  • Row/column matrix

Techniques

Creating an empty M x N matrix

Typically used to initialize the values for traversal or dynamic programming.

  • Make a copy of the matrix with the same dimensions with empty values to store the state

  • When initializing the rows, must use for _ in range rather than * M instead, otherwise, any changes to any of the columns affects every single row

# Create zero matrix
# Inner array is the columns
# Outer array is the rows
zero_matrix = [[0] * len(matrix[0]) for _ in range(len(matrix))]

# Copy matrix
copied_matrix = [row[:] for row in matrix]

Matrix transposition

Rows of a matrix becomes the columns and vice versa.

  • Used when single direction verification can be repeated (verify horizontally, transpose, verify horizontally again)

# *matrix -> return the rows
# zip -> pairs every value in the same position with each other
transposed_matrix = zip(*matrix)

# Bruteforce
transposed = [[0] * len(matrix[0]) for _ in range(len(matrix))]
for i in range(len(matrix)):
	for j in range(len(matrix[0])):
		tranposed[i][j] = matrix[i][j]

Traversing common shapes

Commonly used when the elements of a matrix follow a given property and these elements create a common shape that can be traversed

  • Common shapes include stairs (as seen in Count Negative Numbers in a Sorted Matrix) or pairs

    • Stair traversal: either move 1 row up/down or move 1 col left/right

  • See if can make assumptions about the entire row based on some indicated value (like if first value is < 0, then rest of the row is 0

  • Given the shape or pattern, how do we traverse the matrix (when do we move 1 row up/down, when do we move 1 col left/right)

Treating matrix as flat array

Rather than trying to traverse using two for-loops, traverse in one from 0 to mnmn. See searching a fully sorted 2D matrix for an example of such traversal

  • Given an index i where iāˆˆ[0,mn]i \in [0, mn], then

    • The equivalent row is i // n

    • The equivalent column is i % n

Creating sub-grids

Given a matrix of size N x N, break up the matrix into sub-grids of size M x M

  • Given a coordinate (r, c), then associated sub-grid is (r // 3 * 3, c // 3)

  • Commonly used when trying to calculate a property within sub-grids such as Valid Sudoku

Last updated