Given a matrix of integers, if there are zeros in a particular position, make the whole of the corresponding row & column as zeros. Be as space conservative as possible.
The most straightforward solution to the problem is to have 2 arrays, one for storing the positions of zeros in the rows & the other for the columns. Obviously, we've to do better than this.
We can do the same with a single array too. The basic idea is to scan the matrix either row-by-row or column-by-column. Let's assume row-wise scan for this solution. While doing this scan, mark the columns having zeros in the array. If there's a zero in a row, make the whole row as zeros. After completing the row-wise scan, look at the array for the columns having zeros & make them all zeros in the second pass.
There's a beautiful third solution to this problem. Here we just use 2 variables to store the information required. Scan the first row & the first column and if there is a zero in those, mark the same in the two variables. Now, start scanning without the first row & column. If you encounter a zero, mark the same in the first element of the corresponding row & column as zero. Once this pass is completed, using the information in the first row & column, propagate the zeros to the other rows & columns. Finally, based on the information available in the 2 variables, modify the first row / column as required.
The most straightforward solution to the problem is to have 2 arrays, one for storing the positions of zeros in the rows & the other for the columns. Obviously, we've to do better than this.
We can do the same with a single array too. The basic idea is to scan the matrix either row-by-row or column-by-column. Let's assume row-wise scan for this solution. While doing this scan, mark the columns having zeros in the array. If there's a zero in a row, make the whole row as zeros. After completing the row-wise scan, look at the array for the columns having zeros & make them all zeros in the second pass.
There's a beautiful third solution to this problem. Here we just use 2 variables to store the information required. Scan the first row & the first column and if there is a zero in those, mark the same in the two variables. Now, start scanning without the first row & column. If you encounter a zero, mark the same in the first element of the corresponding row & column as zero. Once this pass is completed, using the information in the first row & column, propagate the zeros to the other rows & columns. Finally, based on the information available in the 2 variables, modify the first row / column as required.
No comments:
Post a Comment