2d-Arrays/Matrices

In programming, we can work with Matrices, which can be created with a 2d Array which is simply arrays nested inside an array (it is also possible to create greater multi-dimensional arrays 3d, 4d by further nesting).

Photo by Nick Fewings on Unsplash

A 2d array would simply look something like this.

[[1,3,9,4],
 [5,7,9,5],
 [1,1,1,2],
 [6,3,8,4]]

We can access elements in this 2d array the same way that we would a regular array with [] just another level deeper so array[i][j] with the i representing the row and the j representing the column. So if we wanted to access the 1 in the top left corner of the above matrix we could get this with array[0][0]. The above example is a square but our matrices can also be rectangles with more rows than columns or vice-versa.

There are several algorithm questions that can be using 2d arrays like spiral through the matrix, search a matrix, rotate the matrix. The matrix question I will focus on and code out a solution is for Sort the Matrix Diagonally. This is a leetcode question (1329). The question asks to sort the values of the matrix diagonally from top left to bottom right in ascending order. So below is an illustration of a matrix(unsorted diagonally) and the arrow shows the direction we want our sorted matrix to go in increasing. The second matrix to the right is the result we want.

To achieve this one trick we have to notice or realize (which is helpful in most questions dealing with matrices and diagonals) is the relationship between the indexes of the matrix. The index of the row and the column are related for each diagonal in a way that the row index minus the column index will be the same value for the whole diagonal. In the above example, the diagonal running through middle 7, 2, 4, 6 the row index minus the column index for all these numbers is 0. Therefore we can use that knowledge loop through the matrix and map out the matrix by each of its diagonals. We can then sort the mapped values of each diagonal line. The last part is then to put back together the matrix sorted from the mapped out values by going through each point in the matrix and placing the sorted value from the map (again using the row index minus the column index). Below is the explained solution coded in JavaScript:

In short, we map out the original matrix diagonally sort the map, and rebuild the matrix from the map.