Unlock the complete
Logicmojo experience for FREE
Sign Up Using
Sign Up Using
Given a two-dimensional array, if any element within is zero, make its whole row and column zero. For example, consider the matrix below.
In the input matrix, at positions (0,0) and (0,3), there are two zeros. The result should be a matrix with zeros in the first row and zeros in the first and fourth columns.
One naive solution that comes to mind is to scan the 2D matrix and, if a zero is found, make the entire column and row zero. However, this is incorrect; even if there is only one zero in the matrix, the entire matrix will be zero.
We can record the row and column numbers of each cell in the matrix that has a zero. In the next cycle, all of the cells in this recorded row and column can be set to zero.
1. We make a pass over our original array and look for zero entries.
2. If we find that an entry at [i,j] is 0, we must record the row i and column j somewhere.
3. As a result, we use two sets: one for rows and one for columns.
4. Finally, we iterate over the original matrix.We examine each cell to see if the row r or column c has been marked previously. We set the value in the cell to 0 if any of them were marked.
Time Complexity : O(M×N) where M and N are the number of rows and columns respectively.
Space Complexity : O(M + N).