LeetCode 73 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.

Challange
Could you devise a constant space solution?

Difficulty
Medium

Similar Problems

[LeetCode 289] Game of Life M

Analysis

We need to record in which row or column that 0 appears.

Idea 1

Time: O(n)
Space: O(n)

Create a helper 1d array of size n to record whether 0 appears or not in the j-th column. When we iterate over the matrix row by row, we set the line to 0 if 0 appears, and set the corresponding j-th element of 1d array to true. Once we done, we iterate over again and set the column to zero according to the helper array.

Idea 2

Time: O(n)
Space: O(1)

We can reuse the visited row (or simply the first row) as our auxillary array. Iterate over the matrix row by row, if 0 appear in the i-th row, set that row to zero, and record the column j in into the first row. We need first to store whether first row has 0 for later use because we may overwrite its value in the iteration as explained above.

1. Cpp solution

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {

        int m = matrix.size();
        int n = matrix[0].size();

        vector<bool> zeroColumns(false, n)
        for(int i = 0; i < m; i++) {
            bool rowHas0 = false;
            for (int j = 0; j < n; j++) {
                if(matrix[i][j] == 0) {
                    rowHas0 = true;
                    zeroColumns[j] = true;
                }
            }
            if(rowHas0) {
                for(int j = 0; j < n; j++) matrix[i][j] = 0;
            }
        }
        for(int j = 0; j < n; j++)
            if(zeroColumns[j])
                for(int i = 0; i < m; i++) matrix[i][j] = 0;
    }
};

2. Cpp Solution

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {

        int m = matrix.size();
        int n = matrix[0].size();

        bool firstRowHasZero = false;
        for (auto e: matrix[0]) {
            if (e == 0) {
                firstRowHasZero = true;
                break;
            }
        }

        for (int i = 1; i < m; i++) {
            bool rowHasZero = false;
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    rowHasZero = true;
                    matrix[0][j] = 0;
                }
            }
            if (rowHasZero) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = 0;
                }
            }
        }

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

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

3. Go solution

func setZeroes(matrix [][]int) {
    m := len(matrix)
    if m == 0 {
        return
    }
    n := len(matrix[0])

    firstRowHasZero := false
    for _, v := range matrix[0] {
        if v == 0 {
            firstRowHasZero = true
            break
        }
    }

    for i := 1; i < m; i++ {
        rowHasZero := false
        for j := 0; j < n; j++ {
            if matrix[i][j] == 0 {
                rowHasZero = true
                matrix[0][j] = 0
            }
        }

        if rowHasZero {
            for j := range matrix[i] {
                matrix[i][j] = 0
            }
        }
    }

    for j := 0; j < n; j++ {
        if matrix[0][j] == 0 {
            for i := 1; i < m; i++ {
                matrix[i][j] = 0
            }
        }
    }

    if firstRowHasZero {
        for j := range matrix[0] {
            matrix[0][j] = 0
        }
    }
}

Reference