Zero out rows and columns in the given matrix


Given a MxN matrix populated with integers including 0s. You have to come up with an algorithm to zero out the column and row of the the 0 element for all such os in the matrix. Write the steps/algo you would follow. Optimize on time and extra space required to do this.


Example:

Possible Solution:
One solution which might cross your mine over the the elements of the matrix and as soon as you encounter a 0, zero out all the rows and columns of that the element’s (i,j) position. This won’t work out as when you zero out the other members which you haven’t even traversed, you would probably meet the zeros you introduced.
One solution could be be:
1. Iterate over the matrix once and put the (i,j) location of all the zeros you encounter.
2. Now iterate over this position list to get those (i,j) positions and zero out the corresponding rows (i’s) and columns(j’s).
Since you have been asked to think on optimizing the algorithm for time and space, One optimization you could do to save more space would be to store just the rows and columns separately so you can avoid storing duplicate  rows or columns. e.g. in the above example the (i,j) positions that you would store would be:
(0,1)
(0,4)
(2,1)
making it a total of 6 storage elements (2 for each position).
On the other hand if you store just the rows and columns separately, you will end up storing:
Rows:
0
2
Columns
1
4
making it a total of 4 storage elements.
If we have many more zeros and a large matrix the optimization would be huge.

0 comments:

Post a Comment