Untitled

mail@pastecode.io avatarunknown
plain_text
13 days ago
2.6 kB
1
Indexable
Never
/* The reason the first row and first column need to be handled separately in this algorithm is to ensure that we don't accidentally zero out the entire matrix when processing these rows and columns.
 */
 /*********************
  we yuse the 1st row and col as markers so we process them seperately
  ****************/

class Solution {
public:
    void setZeroes(vector<vector<int>>& grid) {
        int r=grid.size() ,c=grid[0].size();
        bool frz=false, fcz=false;
        for(int i=0;i<r;i++){
            if(grid[i][0]==0){
                fcz=true;
                break;
            }
        }
        for(int j=0;j<c;j++){
            if(grid[0][j]==0){
                frz=true;
                break;
            }
        }
        //set markers in 1st row and col
        for(int i=1;i<r;i++){
            for(int j=1;j<c;j++){
                if(grid[i][j]==0){
                    grid[i][0]=0;
                    grid[0][j]=0;
                }
            }
        }
        //now solve all except 1st row and col
        for(int i=1;i<r;i++){
            for(int j=1;j<c;j++){
                if(grid[i][0]==0 || grid[0][j]==0){
                    grid[i][j]=0;
                }
            }
        }
        //now set 1st row and col
        if(frz){
            for(int j=0;j<c;j++){
                grid[0][j]=0;
            }
        }
        if(fcz){
            for(int i=0;i<r;i++){
                grid[i][0]=0;
            }
        }
    }
};

/* 
class Solution {
public:
    void set(vector<vector<int>>& grid,int x,int y){
        int i=x; //it is setting the grid 1st time and second time its no onger zero
        while(i>=0){
            grid[i][y]=12;
            i--;
        }
        i=x;
        while(i<grid.size()){
            grid[i][y]=12;
            i++;
        }
        i=y;
        while(i>=0){
            grid[x][i]=12;
            i--;
        }
        i=y;
        while(i<grid[0].size()){
            grid[x][i]=12;
            i++;
        }
    }
    void setZeroes(vector<vector<int>>& grid) {
        int r=grid.size(), c=grid[0].size();
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                if(grid[i][j]==0) set(grid,i,j);
            }
        }

        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                cout<<grid[i][j]<<"-";
                //if(grid[i][j]==12) grid[i][j]=0;
            }
            cout<<"\n";
        }
    }
}; */