# 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)$for a $m \times n$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 $mn$. See searching a fully sorted 2D matrix for an example of such traversal

Given an index

`i`

where $i \in [0, mn]$, 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