[C++] Leetcode 73. Set Matrix Zeroes (Hint, Solution)

Problem

https://leetcode.com/problems/set-matrix-zeroes

Set Matrix Zeroes - LeetCode

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

You must do it in place.

 

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2:

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

 

Constraints:

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

 

Follow up:

• A straightforward 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?

 

 

 

Hint

Try using first row and column to store states of each row and columns.

 

 

 

Solution

Using first row and column as an array, we have another problem:
We can set matrix[i][j] (1<i and 1<j) to zero if matrix[0][j] or matrix[i][0] is zero, but as we already set elements in first column and row to zero, we can't tell if they had zero or not.

Simple solution for this is to make bool variables that tell us if they had zero or not.
This will make space complexity to O(1), since we only have two variables (four if you decided to store size if matrix).

 

 

 

Code

Simple

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        bool isRowHasZero = false;
        bool isColHasZero = false;

        for (int i=0; i<m; i++)
            if (matrix[i][0] == 0)
                isColHasZero = true;
        for (int j=0; j<n; j++)
             if (matrix[0][j] == 0)
                isRowHasZero = true;

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

        for (int i=1; i<m; i++)
            for (int j=1; j<n; j++)
                if (matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;
        
        if (isRowHasZero)
            for (int j=0; j<n; j++)
                matrix[0][j] = 0;
        if (isColHasZero)
            for (int i=0; i<m; i++)
                matrix[i][0] = 0;
        
    }
};

 

Whole Code with Test Case

// https://leetcode.com/problems/set-matrix-zeroes
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        bool isRowHasZero = false;
        bool isColHasZero = false;

        // Check if first row and column has zero
        for (int i=0; i<m; i++)
            if (matrix[i][0] == 0)
                isColHasZero = true;
        for (int j=0; j<n; j++)
             if (matrix[0][j] == 0)
                isRowHasZero = true;

        // Store states of each row and column in the first row and column
        for (int i=1; i<m; i++)
            for (int j=1; j<n; j++)
                if (matrix[i][j] == 0)
                    matrix[0][j] = matrix[i][0] = 0;

        // Set zeros except first row and column
        for (int i=1; i<m; i++)
            for (int j=1; j<n; j++)
                if (matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;
        
        // Set first row and column to zero if they had zero
        if (isRowHasZero)
            for (int j=0; j<n; j++)
                matrix[0][j] = 0;
        if (isColHasZero)
            for (int i=0; i<m; i++)
                matrix[i][0] = 0;
        
    }
};

int main() {
    Solution s = Solution();
    vector<vector<int>> matrix = {
        {0, 1, 2, 0},
        {3, 4, 5, 2},
        {1, 3, 1, 5}
    };
    s.setZeroes(matrix);
    for (int i = 0; i < matrix.size(); i++) {
        cout << "[";
        for (int j = 0; j < matrix[0].size(); j++)
            cout << matrix[i][j] << " ";
        cout << "]" << endl;
    }
}

 

 

 

Complexity

Time

Time complexity will be O(m*n).

 

Space

Space complexity will be O(1).

 

 

 

Best Solution (Pinned)

 

 

 

Overall