The jitters and nervousness of a coding interview is more than real!
No matter how much you prepare for a coding interview, some kind of uncertainty always exists!
From array questions to the longest palindromic substring to binary tree to graph problem to duplicates in array, you can expect several types of questions in a coding interview.
One such topic that holds great importance in a coding interview is set matrix zeroes.
A zero matrix is one whose all the elements are equal to 0. In a set matrix zero, the elements of a given matrix are 0 and you have to find it.
To keep the importance of this topic in consideration, we have curated this blog post.
Read on and fill your knowledge bank!
Set matrix zero
For a given set of matrices with the value 0, you may be required to find the elements. Note that no extra space would be needed in order to perform the operations.
Consider the problem statement;
A matrix is given. If the elements in that matrix are 0, you need to set an entire column and rows to 0 by returning the matrix.
Let’s take an example;
Matrix is [ 1, 1, 1 ] [ 1, 0, 1] [ 1, 1, 1 ]
The output would be [ 1, 0, 1] [ 0, 0, 0 ] [ 1, 0, 1 ]
Explanation: As the matrix [ 2, 2] = 0. You can set the 2nd column and the 2nd row as the 0.
Approaches to follow
Brute force approach
While using the brute force approach, the common mistake that you may commit is to traverse the matrix for any given 0. You can update all the values in the rows or columns as 0. The solutions in this case may seem quite easy but it can lead to some of the wrong solutions.
The correct solution idea to follow:
One way would be to create the auxiliary matrix which is of the same size and gets filled with 1s. You can make the necessary changes in this auxiliary matrix to copy it with the original matrix in the end.
You may need to search for the zeroes in an original matrix in order to update all the rows or columns in the auxiliary matrix.
Follow these steps:
- At first, you need to create the temporary matrix of the size M *N to initialise it at all the needed places with a 1
- Then scan an original matrix. In case, the A [i] [j] == 0, you can set at all the positions of the row i and the col 1 with a 0 in the new matrix
- Copy all the desired elements from your temporary matrix into the original matrix
Simply in a brute force approach, you may need to identify all the zeroes. For every zero detected, you can change all the elements except that zero in a row or a column to get the – 1.
The complexity analysis
For all the cells, you may need to traverse the rows or columns with the total of N*M cells.
The time complexity in this case would be O [N *M ( N +M )]
However, the space complexity will be O [N / M] to store the given auxiliary matrix.
Using the hash tables
Another approach to follow for finding the set matrix zeroes is by using the hash tables. Here, you are not using the auxiliary matrix to store the rows or columns that need to be updated.
You can create the hash tables for all the desired columns and rows to later update them as true. This is the signal for us to update any particular row or column with its value as 0.
The solution steps to follow in this case are:
- Create any two hash table rows and columns respectively. Of the size M and N
- Now, you can initialise all the given values of rows [] and col[] to consider it false
- Now you can iterate over a matrix for the A [i] [j] == 0 with the set row [i] = true col[j] as true
- After you complete step 3, iterate again through the matrix A for the given A [i] [j] , if you get the row [i] and the col [j] would be true, update the A [i] [j] to be 0.
The time complexity, in this case, would be as such where you need to create or fill the values of two given hash tables + traverse the matrix + update the given matrix
The space complexity in this case would be the O [M + N] to store the hash tables.
Using the in-place hashing
You may need the extra space for storing rows and columns in a hash table. In this case, we would be able to optimise the space in a way that will help you store the rows or columns in that particular matrix.
Use the first row or the first matrix for storing the status of your rows and columns. The problem may occur in the case of the first row or matrix where you need to handle two variables.
The steps to follow in this case are:
- Initialise the given first row or column as false and the two variables will store the status.
- You can use the first row or the first column to your hash in order to store the status of that row or column.
- Iterate over the whole matrix
- Now you can update the values for storing the matrix except in the case that the first row or the first column needs to be 0
- Update the value of your first rows and first columns
The time complexity in this case would be
Checking the first row and columns + traversing or updating the matrix + updating the first row and column
The space complexity in this case will be O [1]
Wrapping Up
From duplicates in arrays to string questions to binary tree questions, you may encounter several types of questions in a coding interview.
In this blog, we explained the concept of set matrix zero. Keep this blog as your mentor and fill your knowledge base in the right direction.
Happy learning!
