Given an m x n integer matrix mtx[][], if an element is 0, fill its entire row and column with 0's.
Input: mtx[][] = {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}}
Output: {{0 0 0 0} {0 4 5 0} {0 3 1 0}}
Input: mtx[][] = {{1, 0, 3}}
Output: {{0, 0, 0}}
Solutions
Method 1: In O(m*n) time and O(1) space
In this approach, we can get the solution in constant space O(1) only.
The idea is to use the first column and first row of the matrix as columns[] and rows[] arrays to store rows and columns to be zeroed.
This solution is based on the fact that we traverse the matrix row by row (0,0 -> 0,1 ...0,n-1 ....1,0, 1,0). While traversing this way, once a block (i,j) is traversed, we don't need to see that block to decide whether this column or row needs to be zeroed.
The only issue is the top-left block (0,0). This block is part of both the first column and the first row. So, if there is a zero in the first row but not in the first column, this will make both the first row and the column zero. This is because as soon as the first zero is found in the row, this 0,0 block will be marked to make zero in the first row, but this 0,0 being common for both the first row and the first column, will also be read by the first column and hence the first column will also be zeroed.
To overcome this, we need an extra variable to hold 0,0 for the first column. The original 0,0 will be used by the first row.
Complexity
The time complexity of this solution is O(m*n) and space complexity is O(1).
Method 2: In O(m*n) time and O(m+n) space
In this approach, we will use two arrays of length n and m to store rows and columns to be zeroed.
The idea is to iterate the matrix twice.
In the first iteration, identify rows and columns that need to be zeroed and store them in tmp arrays rows[] and column[].
Iterate over the matrix one more time and if for any block (r,c) there is an entry in rows[r] or column[c], mark the element 0.
Complexity
The time complexity of this solution is O(m*n) and space complexity is O(m+n).