Intro
A Matrix is a 2-dimensional array, arrays nested within an array.
Think of the inner arrays as rows and the elements’ within indices correspond with the value of that row at certain column. E.g. x= matrix[i][j] , here i is the index of the array (the row) and j is the index of the element (column) in it.
Matrices play a big role in DynamicProgramming and GraphTraversal. They can also be used to represent Graphs where each node is a cell in the matrix and has 4 neighbors (except the edge and corner cells). For more on this refer to Graphs
Edge cases
Consider these edge cases whenever dealing with matrices.
- Empty matrix. Check that none of the arrays are 0 length
- 1 x 1 matrix, a single cell.
- Matrix with only one row or column.
Techniques
Creating an empty N x M matrix
For most traversal or DynamicProgramming questions, you’ll likely want to copy the matrix with the same dimensions but initialized to empty values to store state or computed values for Dyno prog. // Be familiar on how to do this in your language of choice.
# One liner using List comprehensions
zero_matrix = [[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]Copying a matrix
matrix_copy = [row[:] for row in matrix]Transposing a matrix
Transposing means to switch the columns for rows and vice versa. This is great for when you need to check conditions both vertically and horizontally such as in many grid-based games (Tic-Tac-Toe, Connect 4 and Crosswords to name a few), so just code the logic for one orientation then transpose the grid and check. In python this is as simple as:
transposed = zip(*matrix)// Kinda uninformative, so basically what you want to do is to grab all the elements in a column, and place them in a row in a new matrix. Such that all of column 1 in matrix1 become the elements in row 1 in matrix2.
Essential questions
Recommended practice questions
Try these after completing the essentials.