Problem solving with programming: Setting the matrix elements to zero

Problem solving with programming: Setting the matrix elements to zero

Given a matrix of size m * n, write a program to fill zero in i^th row and j^th column if matrix[i][j] is zero.

For example let us consider the following matrix.

[ 

  6 0 2

  1 3 4

  5 9 0

]

It should transform to the following.

[ 

  0 0 0

  1 0 0

  0 0 0

]

This problem looks simple at the first glance, but if we do not write the program carefully it results in the wrong output, typically marks all the elements in the matrix to zeros.

So a wrong solution can be iterate through all the elements of a matrix, and whenever we found a zero, set the corresponding rows and columns as zero.

This will have undesired effect. Since we are modifying the same matrix, it is possible that an unexplored element may be set to zero because of a zero in the same row or column. So it is not possible to solve this problem in just one iteration.

An inefficient, but correct solution could be to create a temporary matrix which is a copy of the original matrix, and mark the elements in temp instead of the original. This will take O(m*n) extra space.

Can we solve this more efficiently?

Read full article from Problem solving with programming: Setting the matrix elements to zero