Problem

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

Intuition

Instead of using two extra matrices row and col, we will use the 1st row and 1st column of the given matrix to keep a track of the cells that need to be marked with 0. But here comes a problem. If we try to use the 1st row and 1st column to serve the purpose, the cell matrix[0][0] is taken twice. To solve this problem we will take an extra variable col0 initialized with 1. Now the entire 1st row of the matrix will serve the purpose of the row array. And the 1st column from (0,1) to (0,m-1) with the col0 variable will serve the purpose of the col array.

Approach

Described in the comments

Complexity

• Time complexity:O(2*(N+M))

• Space complexity:O(1) as we are not using any extra space

Code

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int col0 = 1; // this is the first block of the first column which is SETUPPED on the top of 1st block,
        //represeting the 1st column, if any value in the column 1st is zero, then this will change not the 
        //not the first column of first block.

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

        //1st step is, we are considering the col[0] = rows or rows[i] and row[0]=col[m] and col[j]=1; 
        //means we are considering setting the flag, if the row and column has zero, we will set the flag 
        //in the first column and row.

        for(int i = 0 ;i<n;i++)
        {
            for(int j=0 ; j<m ;j++)
            {
                if(matrix[i][j]==0)
                {
                    matrix[i][0]=0; // we are flaggin the first row.

                    //now see, we have had col0, which is represeting column 1st, so what about other columns?

                    if(j==0) // if we have 0 in first column then we change the value 
                    {
                        col0=0;

                    }
                    else if(j!=0) // else for the rest of the rows 
                    {
                        matrix[0][j]=0;
                    }
                }
            }
        }

        //now check the inner block, rows and columns apart from the 1st rows and columns, cuz we have checked 
        //we have checked in the above, and we are checking this beacuse if not it can do the issue, if the 1st block
        //changes to zero, it will change the last block of 1st row, which makes tough and incorrect.

        for(int i=1 ; i<n; i++)
        {
            for(int j=1 ; j<m ;j++)
            {

                if(matrix[0][j]==0 || matrix [i][0]==0) // now we check flag, as we did in the previous "Better" solution, acc to that flag change the value 
                {
                    matrix[i][j]=0;
                }

            }
        }

        // now what left, 1st row and 1st column, we can not change this before, because it will affect the answer

        if(matrix[0][0]==0) // this will change the 1st row , represting the 1st row
        {
            for(int j = 0; j<m; j++) matrix[0][j]=0;
        }
        if(col0==0)      // this is representing the 1st column 
        {
            for(int i=0; i<n ;i++) matrix[i][0]=0;
        }



    }
};