Ace Your Coding Interview — Blind 75 Solved and Explained — Part 7 Matrix

7 min readAug 3, 2022

This week we are looking at 2d matrices. This is another crucial subject in the interview process that is heavily used by many companies. The Blind 75 includes four questions for matrices. However, I urge you to find 10–15 more questions, making sure you are confident in solving a variety of problems.

Blind 75 LeetCode Questions - LeetCode Discuss

leetcode.com

Question 1 — Set Matrix Zeroes

Set Matrix Zeroes - LeetCode

leetcode.com

This question unexpectedly fools you. The key thing is to figure out that we need to find a way to track the rows and columns that need to be zeroed instead of actively changing as we loop. So we utilize the first column and row as a way to indicate if that row/column itself needs to be modified.

Our Approach:

We start by declaring our variables. This includes the length of the rows and columns as well as a boolean flag to indicate whether the first column needs to be converted to 0s.
Our first loop iterates through the rows. During each iteration, we check if the row starts with zero. If this is true, we set our isCol variable to true as the first column needs to be zeroed out.
Within our first loop after finishing the column check, we loop through the columns in the row. During each iteration, we check if the current cell has a value of zero. If zero, this means we need to set the column and row of that cell to zeroes. To start this process, we set the first element of the corresponding row and column to zero. The reason we have done this is so that once done checking, we can refer to the first column and row to determine any cell value — whether a zero or no changes.
Next, we iterate through the matrix input starting at the second index for both the columns and rows. During each iteration, we check if the first element of the row or column is zero. This indicates that our element needs to be zero.
Finally, after being done with the inner matrix starting at the second index, we fix the first row and column. If true, we check the leftmost corner of the matrix. We use this information to set the first row to be filled with zeroes. We proceed by checking our flag to determine if our first column needs to be zeroed out. After completing the process, our matrix is now modified to fit all our needs.

Question 2 — Spiral Matrix

Spiral Matrix - LeetCode

leetcode.com

Solution Inspired By: https://leetcode.com/problems/spiral-matrix/discuss/20599/Super-Simple-and-Easy-to-Understand-Solution/185257

The spiral matrix question is best solved when the necessary pattern is figured out. As seen in the picture during the description below, we follow 4 sets of motions; upon the completion of these motions, we get closer to the center and repeat until our list is full.

Our Approach:

We start by declaring our variables. Create a list to store the spiral order, obtain the row and column length of the matrix, and four variables to help visualize the spiral order — up, down, left, and right. Set the visualization variables to be the start and end for their position. So left and right should be the starting and final index of rows, meanwhile, up and down should be the starting and final indexes for columns.
Check if the matrix is null or empty. If so, return an empty list.
We perform a set of operations until our result list size is equal to the size of the matrix.
As you can see, we need to start from the leftmost corner and work our way to the rightmost point. As we do this, we add each visited cell to the results list. Next, we go from the rightmost corner down to the right bottom corner. This is followed by the right bottom to the left bottom, then finally, the left bottom to one cell before the top left. These 4 operations can simply be accomplished by utilizing for loops.

5. Now come to the trickier parts, we have circled the outmost values we have to spiral inwards so we can do the same until we reach the center of our matrix. In the example above, the matrix isn’t large, however, you can see how if we had a 10x10 matrix per se we would have to go through multiple spirals before reaching the center. To accomplish this, we adjust our limit values of up, down, left, and right. All the values have to be shifted towards the center. Up will come down one, down will go up one, left will move right one, and right will move left one index. With these operations, all our points have gotten closer to the center.

6. With these new adjusted points, we can repeat our while loop until we have a list matching the size of the matrix.

Question 3 — Rotate Image

Rotate Image - LeetCode

leetcode.com

Solution Inspired by: https://leetcode.com/problems/rotate-image/discuss/18879/AC-Java-in-place-solution-with-explanation-Easy-to-understand.

This is a rotation method I’ve seen a few times. It is not as intuitive, but I find it to make a lot more sense for me. It utilizes transposition as well and a horizontal flip to achieve our goal. I will also link the leetcode solution below, which includes a video tutorial to walk you through a solution step by step.

Our Approach:

Get the length of our matrix, to be used in the traversal of strings
The first traversal of our matrix is to transpose the elements. This essentially means we are swapping column and row indexes. So matrix[row][col] becomes matrix[col][row] for each cell.
The second traversal is a horizontal flip of the matrix. Now we do a horizontal flip so we can rotate the elements towards the right. If we vertical flipped the element, it would rotate towards the left side. We can once again traverse the matrix and swap the cell value with the value on the horizontally symmetric matrix.

Question 4 — Word Search

Word Search - LeetCode

leetcode.com

Solution Inspired By: https://leetcode.com/problems/word-search/discuss/27811/My-Java-solution

If you take anything from this article, really focus on understanding this question. I have personally seen a version of this question multiple times in different companies' interviews. Once again, understanding depth-first search is a key algorithm to solving a variety of questions. In our 2d matrix, we loop through to find a starting point for our word search and feed it to our dfs algorithm to see if we find the word.

Create a global boolean map to store visited cells.
Iterate through the matrix, for each cell check if the current cell is equal to the starting character of the word that is being searched. If this is true, we initiate a depth-first search to find if the word exists.
We call our standard depth-first search; we start by checking if our current index is equal to the length of the word. This is because if the length of the word equal to the index indicates we have reached the end of the word successfully, therefore the word is found and true is returned.
We run the following checks to make sure our current cell is valid for continuing the depth-first search: the row index must not be out of bounds, the columns must not be out of bounds, the word must not be previously visited and the current point in the board must be the corresponding value to the index of the character being searched.
If our statements pass we must declare the cell as visited for future reference.
Recursively call depth-first search to search up, down, left, and right while making passing the index + 1 so we can progress on the word character index.
Following this no recursive calls return a valid point, we set our visited map to false to reset it into its original shape and return false on the method as the word isn’t found.