Write an algorithm such that if an element in an MxN matrix is 0, its entire row and
column is set to 0
My first thought to simply iterate through the matrix, and when it hit a zero, then set the entire row/col to zero. The problem, I quickly realized, is that this would cause the algorithm to make the entire matrix set to zero, because it will keep hitting zeroes.
Therefore, you need to track the zeros separate from the actual matrix. So we need a second matrix. But do we really need a second matrix? After all, all we need to know is that if there is at least one zero in that row, not the exact positions of the zeros in the row. So, I'm going to go for 2 arrays rather than 1 whole matrix.
No comments:
Post a Comment