Set Matrix Zeroes [Logic + Solution] in bits

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

You must do it in place.

• According to GFG, in place is an algorithm that does not need extra space and produces an output in the same memory that contains the data by transforming the input ‘in-place’.
• However, a small constant extra space used for variables is allowed.

Example:

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

---

Basic Logic!

• When you carefully think at first sight you may decide to track each 0 to the specified index from the row and column perspective.
• You will create two different arrays/vectors for the row and column acc. to the size of the matrix.
• Here, we initialized the vectors as -1, because there will be no negative value in the test case, " easy to compare ".

vector<int> row(matrix.size(),-1); // (initialised_size, all_values in vector)
vector<int> col(matrix[0].size(),-1);

• Now mapping each '0s' and the index to store it in our vector row and col.

for(int i = 0; i<matrix.size();i++){
      for(int j = 0; j<matrix[0].size();j++){
            if(matrix[i][j]==0){
                row[i]=0;
                col[j]=0;   
            }
      }
}

• Now, Check the index from the row and column having 0, on true we have to set the value 0 of the same index.

for(int i = 0 ; i<matrix.size();i++){
      for(int j = 0; j<matrix[0].size(); j++){
            if(row[i]==0||col[j]==0){
                matrix[i][j]=0;
            }
      }
}

• As we have to transform the value to 0 on the index having pre-assigned 0 in the

---

Sigma Logic!

In this logic, we are concentrating on "in-place algorithm", using the space from the defined matrix only.

In the Basic logic, we assigned 2 vectors, through which we suffered from space complexity, on noticing we had to change the value to 0 of the index we found 0 from any rows or col.

for(int i = 0; i<matrix.size(); i++){
      if(matrix[i][0]==0) col0 = 0; // why this ( next point ) ->
          for(int j = 1; j< matrix[0].size(); j++){
                if(matrix[i][j]==0){
                    matrix[0][j]=0;
                    matrix[i][0]=0;
                }
        }
}

• While making the 0th row and column as an index tracker, we caught an error of duplicating the value at matrix[0][0].
• After the "if" condition, the nested loop will start like this: matrix[0][1] and so on...
• And if the loop detects 0 it will change the 1st row and column of the same index in perspective of the matrix's row and column index with 0.
• As the same index has to be 0 in future, so it doesn't affect but helps as a tracker.

the main part, now!

for(int i = matrix.size()-1; i>=0; i--){
      for(int j = matrix[0].size()-1; j>=1 ; j--){
            if(matrix[0][j] == 0 || matrix[i][0] ==0){
                matrix[i][j]=0;
            }
       }
        if(col0 == 0) matrix[i][0]=0;
        cout<<endl;
}

• Did you notice? we started mapping the index in reverse order. Because we already transformed the 1st row and column and now we have to do the comparison.

• Mapping from the last row to the first column, while starting the 2nd column to the last column.

---

CODE

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int col0 = -1;

        for(int i = 0; i<matrix.size(); i++){
            if(matrix[i][0]==0) col0 = 0;
            for(int j = 1; j< matrix[0].size(); j++){
                if(matrix[i][j]==0){
                    matrix[0][j]=0;
                    matrix[i][0]=0;
                }
            }
        }

        for(int i = matrix.size()-1; i>=0; i--){
            for(int j = matrix[0].size()-1; j>=1 ; j--){
                if(matrix[0][j] == 0 || matrix[i][0] ==0){
                    matrix[i][j]=0;
                }
            }
            if(col0 == 0) matrix[i][0]=0;
            cout<<endl;
        }

    }
};

Now we understood the code in chunks 🤩.

Question link on leetcode.