Here are the summaries for the Matrix algorithms in Leetcode's Blind 75. Check out the previous post on Linked Lists. A matrix is a 2 dimensional data structure consisting of rows and columns. For these problems, the matrix is represented with an array of arrays.

Set Matrix Zeroes

Given a matrix of integers, size m x n, if an input value is 0, set all values from its row and column to 0 as well.

Solution with O(m*n) time / O(1) space

We’ll need several separate loops to solve this more efficiently than brute force, but remember when calculating time complexity, only the loop with the highest time complexity is considered.

The trick to getting O(1) space complexity is by using the first row and column of the input matrix to keep track of which rows and columns to fill with 0s. The first thing we need to keep in mind about this solution is that: we will have no way of knowing whether a 0 was originally in the first row or column, or whether we added it later, so we can just have 2 boolean variables to keep track of this.

First we will iterate through the first row, and if there’s a 0 in it, save that to the boolean mentioned above. Do the same thing for the first column.

Then, iterate through the rest of the matrix, copying any 0s to the first row and column.

Iterate through the entire matrix again (except the first row and column), this time use the 0s in the first row and column to set the 0s in the rest of the matrix.

Finally, if there was a 0 in the first row, set the first row to all 0s, and do the same for the first column.

Spiral Matrix

Given a matrix, size m x n, return an array of all values in the matrix ordered by a spiral pattern on the matrix. If you’re visualizing the matrix with the increasing row index going down, and increasing column index going right, the spiral pattern starts at the top left, and moves clockwise, starting with the outermost values, and “spiraling” inward.

Solution with O(m*n) time / O(1) space, where the result array isn’t counted towards space complexity

No tricks with this one except just putting the proper boundaries in place to avoid duplicates and determine when to stop.

Iterate through in the order: right, down, left, up, repeat… keeping track of the min/max row and column “boundaries” to avoid going to the same values again. Stop when the boundary indexes are equal.

Rotate Image

Given a square matrix, size n x n, rotate it 90 degrees clockwise, in-place.

Solution with O(m*n) time / O(1) space

This is a fairly complex problem to solve in-place, because you need to determine the smallest possible sub-problem of a 2 dimensional rotation, not really intuitive, at least for me.

The smallest sub-problem is a rotation of 4 elements at a time, so that after rotating those 4 elements, all of them are in the correct place. For example, one rotation would be moving these cells like so:

(0,0) → (0,n) → (n,n) → (n,0) → (0,0)

where you only need to save one value as you're doing to the rotation.

Given the sub-problem, there are technically several ways to iterate through the matrix, but the main thing to understand is that for each rotation, we need to know a few things to pinpoint the locations:

• Depth offset: Each rotation will happen at a certain depth from the outside edge, e.g. every rotation in the outer edge can ignore every other number in the matrix.
• Rotation offset: For each depth, we can iterate over the sides, where the rotation offset is used to determine which value from each side we are rotating.

For each depth, we can iterate over the sides like so:

• The top side increases from left to right, adding the rotation offset to the column
• The right side increases from top to bottom, adding the rotation offset to the row
• The bottom side increases from right to left, subtracting the rotation offset from the column
• The left side increases from bottom to top, subtracting the rotation offset from the row

Similar to the Spiral Matrix problem above, when we increase the depth within the matrix, we need to set a boundary using the depth to avoid rotating the same values again.

When the depth offset is half of the side length, meaning we're at the center, then we’re done.

Word Search

Given a matrix of characters, size m x n, determine if the specified word exists in the matrix as adjacent cells (in any direction).

Solution with O(m*n*4^w) time / O(w) space, where w is the length of the word

This is more intuitive since the best solution I could find is similar to how you would look for a word manually: look through all cells in the matrix for the first letter in the word, and if you find it, look at all adjacent cells for the next letter, and so on.

First we start the iteration over all cells in the matrix. Whenever we find the first letter in the word, use a depth-first search to recursively see if we can find the full word (this algorithm is called backtracking):

• The base case is just checking if we’ve already found the last letter in the word, and if so, we know the word exists within the matrix.
• Otherwise, if the letter is correct at this point, check all adjacent cells recursively, making sure to avoid going out of bounds.
• The thing to keep in mind for the backtracking is that you can’t reuse the same cells to construct the word. One way to solve this is by temporarily updating “used” cells to be blank within each level of the depth-first search, and changing them back after the recursive call.

Continue until you looked at every cell, or you find the word.