As I continue my job search and interview prep, I’ll be writing about some of my algorithm explorations along the way. Today I’ll be exploring and solving the Zero Matrix problem from binarysearch.io.
The question asks us to define a function that will take in an array of arrays, a matrix, and for every zero in the array, the other elements in the row and column that that zero was in will become a zero too. For example:
In the third array in index 0, there is a zero. Therefore, every element at index 0 will be turned into a zero, as well as every element in the “row” of the third array, and so on and so forth.
The Solution
In order to solve this, we’ll need to check each element in each array and compare the elements in their respective arrays (rows) and index positions (columns). We have two big steps; figure out where each zero is and record it, then replace all the elements in the zero’s row and column. Because we need to check an element in its row as well as its column, our best bet is to use a nested loop. We’ll actually need TWO; one to record where every zero is, and one to do the replacing.
First, we’ll make two arrays, called rowArr and colArr. These will, as you can imagine, store where the zeros are in the rows and the columns. Then our nested loop will iterate through each element in each nested array, and if the element is zero, we push the index (which will be represented as the incrementer) into the respective array:
In the above code, i represent which array we are in, therefore the row, and j represents the column or index position.
Next, we will write a simultaneous nest loop. These loops will go over the matrix and will check if their respective incrementors are in the rowArr and colArr. If they are, then that means that a zero at that index position or row must have been in the original matrix and thus we replace it with a zero. After this is finished, we simply return our mutated matrix.
Because of the nested loops, our function runs at 0(n²). If anyone can come up with a faster solution, let me know!
