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 for a matrix
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
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)
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 . See searching a fully sorted 2D matrix for an example of such traversal
Given an index
i
where , thenThe 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