In a matrix put 0 in the row and column of a cell which contains 0 without using extra space

Question

Given a matrix, if a cell contains 0, then we have make entire row and column corresponding to the cell as 0. For example, if

      1 2 3
M  =  0 4 5
      4 2 0

then the output should be

      0 2 0
      0 0 0
      0 0 0

The method I thought is as follows

1. Make auxiliary arrays row[] and col[]. If a cell(i,j) contains 0 then, mark row[i] and col[j] as 0.(Initially row[] and col[] contains all 1s).
2. Again traverse the whole matrix, if for cell(i,j), either of row[i] or col[j] is 0, then put cell(i,j) as 0.

This takes O(m*n) time and O(m+n) space.

How to optimize it further specially in terms of space.Any suggestions for improving time complexity are also welcomed.

Answer 1

Aha, this is an old question.

1. Use one boolean variate(isZeroInFirstRow) saving if first row has zero element(s) or not and one boolean variate(isZeroInFirstCol) saving if first column has zero element(s) or not.

2. Then, traverse the whole matrix. If cell(i,j)==0, then set cell(0,j) and cell(i,0) to 0.

3. Traverse the first row of the matrix. If cell(0,j)==0, then set all elements in column(j) to 0.

4. Traverse the first column of the matrix. If cell(i,0)==0, then set all elements in row(i) to 0.

5. If isZeroInFirstRow==true, set all elements in row(0) to 0.

6. If isZeroInFirstCol==true, set all elements in column(0) to 0.

Answer 2

You can solve this in O(1) space. One solution is to iterate on the matrix, for each 0 you see, you fill the corresponding row/col with some character, 'X' for example.

When you finish, you should have something like that:

    X 2 X
M=  0 X X
    X X 0

Then you iterate again on the matrix and replace each 'X' with 0 to get:

    0 2 0
M=  0 0 0
    0 0 0