Set Matrix Zeroes Leetcode Solution

Problem Statement

The Set Matrix Zeroes LeetCode Solution – “Set Matrix Zeroes” states that you’re given an m x n integer matrix matrix.We need to modify the input matrix such that if any cell contains the element  0, then set its entire row and column to 0‘s.

You must do it in place.

Example:

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

Output: [[1,0,1],[0,0,0],[1,0,1]]

Explanation:

• The above matrix contains the zero at position (1,1).
• Hence, we need to make the entire 1st row as well as the 1st column zero.

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]]

Explanation:

• The above matrix contains zero’s at positions (0,0) and (0,3).
• Hence, we need to make the entire 0th row,0th column, and 3rd column zero.

Approach

Idea:

1. The main idea to solve this problem efficiently in O(1) extra space is to use the 0th row and 0thcolumn to track which rows and columns will be marked with all zeroes.
2. matrix[i][0]==0will denote that the entire ith the row should be marked with 0‘s.
3. matrix[0][j]==0will denote that the entire jth the column should be marked with 0‘s.
4. First iterate in the 0throw and0thcolumn and check whether there exists a zero. Store the results in the boolean variable f1 and f2.
5. Now, iterate in the remaining rows and columns and mark the respective matrix[i][0]and matrix[0][j]if (i,j)cell contains 0.
6. Now, we need to modify the input matrix.
7. Iterate for all the rows and columns except 0th row and 0thcolumn and set 0 if required using the data from matrix[i][0]and matrix[0][j].
8. Finally, use boolean variables f1 and f2 to mark 0th row and 0thcolumn.

Code

Set Matrix Zeroes Leetcode C++ Solution:

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        bool f1 = false,f2 = false;
        int n = matrix.size(),m = matrix.back().size();
        for(int i=0;i<n;i++){
            if(matrix[i][0]==0){
                f1 = true;
            }
        }
        for(int j=0;j<m;j++){
            if(matrix[0][j]==0){
                f2 = true;
            }
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                if(matrix[i][j]==0){
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                if(matrix[i][0]==0 || matrix[0][j]==0){
                    matrix[i][j] = 0;
                }
            }
        }
        if(f1){
            for(int i=0;i<n;i++){
                matrix[i][0] = 0;
            }
        }
        if(f2){
            for(int j=0;j<m;j++){
                matrix[0][j] = 0;
            }
        }
    }
};

Set Matrix Zeroes Leetcode Java Solution:

class Solution {
    public void setZeroes(int[][] matrix) {
        boolean f1 = false,f2 = false;
        int n = matrix.length,m = matrix[0].length;
        for(int i=0;i<n;i++){
            if(matrix[i][0]==0){
                f1 = true;
            }
        }
        for(int j=0;j<m;j++){
            if(matrix[0][j]==0){
                f2 = true;
            }
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                if(matrix[i][j]==0){
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                if(matrix[i][0]==0 || matrix[0][j]==0){
                    matrix[i][j] = 0;
                }
            }
        }
        if(f1){
            for(int i=0;i<n;i++){
                matrix[i][0] = 0;
            }
        }
        if(f2){
            for(int j=0;j<m;j++){
                matrix[0][j] = 0;
            }
        }
    }
}

Complexity Analysis for Set Matrix Zeroes Leetcode Solution

Time Complexity

The time complexity of the above code is O(M*N) where M = number of rows of matrix and N = number of columns of the matrix.

Space Complexity

The space complexity of the above code is O(1) since we aren’t using any extra space.