Set Matrix Zeros (LintCode/LeetCode)

Meeting the Challenge of Solving In-Place with Constant Storage O(1)

Problem

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Have you met this question in a real interview? Yes

Example

Example 1:

Input:[[1,2],[0,3]] Output:[[0,2],[0,0]]

Example 2:

Input:[[1,2,3],[4,0,6],[7,8,9]] Output:[[1,0,3],[0,0,0],[7,0,9]]

Challenge

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

How to Start?

Let’s just focus on the challenge. We need to do it based on constant storage space, no matter how the size of the matrix changes.

One way is just to rely on the spaces in the matrix itself. Let’s see an example below.

We will store the information of whether each row or column needs to be zeroized by setting to zero using the first column and first row.

But before we do that , let’s contemplate what happen if the zeros are already in the cells in the first column and first row. In the example below, we note that cell (0,1) and (2,0) are zeros. So at the final state of the matrix, row 0 (first row) and column 0 (first column) would need to be all zeros. How do we achieve this? That’s the clever part. We need extra storage spaces, one for marking whether the first column and one for marking whether the first row, would need to be zeroized. Why two storage spaces and not one? Well, imagine we used cell (0,0) to store this information if row 0 has some zero cells, but column 0 has no zero cells. What will happen is that we will end up zero-zing the first column and first row, instead of just the first row.

Importantly, the extra spaces will not grow no matter the size of the input matrix. Hence, this fulfil the challenge: to use constant storage space O(1)…actually somewhat like O(2).

The Algorithm

Let’s start with the cells in the first row and first column. If there are cells in the first row that are zero, set the extra storage cell (0,-1) to zero. If there are cells in the first column that are zero, set the extra storage cell (-1,0) to zero? The extra storage cells are only referred as (0,-1) and (-1,0) so as to align with the picture. They can be just named as two variables and not extension of the matrix grid.

Once we are done with examining the first column/row for zeros cell, we moved on to the inner core cells, see the red boxed cells. If any is zero, we will set the cell in the corresponding first column and first row to zero. So because cell (1,2) is zero, we set cell (0,2) and cell (1,0) to zero.

Now for the penultimate step: we look at cells in the first column and first row that are zero (they could zero be in the matrix all along, or just set to zero by the last step), and then set the corresponding whole row or whole column to zero.

The epilogue is just using the extra storage space and if they are zero, zeroized the first row or first column completely. There we have it.