LeetCode Set Matrix Zeroes: O(1) Space

Overview

LeetCode Set Matrix Zeroes could be solve with O(1) Space cost by using the first column and the first row and one more to store the zero setting information.

LeetCode Set Matrix Zeroes

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

Follow up: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?

Solution: O(1) Space

It is not hard to think of using O(m+n) space and the following code is accepted LeetCode OJ to pass this  Set Matrix Zeroes problem

class Solution {
    public:
       void setZeroes(vector<vector<int> > &matrix) {
            int m = matrix.size();
            if (m < 1)
                return ;
            int n = matrix[0].size();

            vector<bool> row(m, false);
            vector<bool> col(n, false);

            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (matrix[i][j] == 0)
                        row[i] = col[j] = true;
                }
            }

            for (int i = 0; i < m; ++i)
                if (row[i])
                    fill(matrix[i].begin(), matrix[i].end(), 0);

            for (int j = 0; j < n; ++j)
                if (col[j]) {
                    for (int i = 0; i < m; ++i)
                        matrix[i][j] = 0;
                }
        }
};

Then think a bit further, instead of using ADDITIONAL O(m+n) space, we can just the first row and the first column of the given matrix to store the information we need because we only need to know the row and the column numbers to be set as zero which only need O(m+n) space and the if a row i needs to be set as zero then matrix[i][0] could be set to zero, even if it is originally non-zero, there is no harm to do so since it needs to be set
to zero anyways.

The special carefulness needs to be taken when updating the first row and the first column, one should use the original information to determine if we need to set them as zero, rather than use the information after the first row and first column are updated (remember we use them to store other information, so we will change the first row and first column), here is where we need the constant memory to store the original information about first row and first column. The following code implements this idea and is accepted LeetCode OJ to pass this  Set Matrix Zeroes problem:

void setZeroes(vector<vector<int> > &matrix) {
    int m = matrix.size();
    if (m < 1)
        return ;
    int n = matrix[0].size();

    int row0 = matrix[0][0];

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (0 == matrix[i][j]) {
                matrix[0][j] = 0;
                if (0 == i)
                    row0 = 0;
                else
                    matrix[i][0] = 0;
            }
        }
    }

   for (int i = m - 1; i >=0; --i)
        for (int j = n - 1; j >=0; --j) {
            if (0 == i) {
                if (0 == row0 || 0 == matrix[0][j])
                    matrix[i][j] = 0;

            }
            else {
                if (0 == matrix[i][0] || 0 == matrix[0][j])
                    matrix[i][j] = 0;
            }
        }

}

Summary

LeetCode Set Matrix Zeroes could be solve with O(1) Space cost by using the first column and the first row and one more to store the zero setting information.

Written on May 20, 2013