Advertisement
imashutosh51

Modify Boolean Matrix

Jul 23rd, 2022 (edited)
50
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.54 KB | None | 0 0
  1.  
  2. //Methodd 1:TC = O(N*M) and space complexity O(N+M)
  3. //LOGIC:we sill store all the rows in map which have 1 atleast one and same for col.
  4. //after that traverse the matrix,make the (i,j) box=1 if i is in row map,or j is in col map.
  5.   void booleanMatrix(vector<vector<int> > &matrix)
  6.      {
  7.          unordered_map<int,int> row,col;
  8.          for(int i=0;i<matrix.size();i++){
  9.              for(int j=0;j<matrix[i].size();j++){
  10.                  if(matrix[i][j]==1){row[i]=1;col[j]=1;}
  11.              }
  12.          }
  13.          for(int i=0;i<matrix.size();i++){
  14.              for(int j=0;j<matrix[i].size();j++){
  15.                  if(matrix[i][j]==0 && (row[i] || col[j])) matrix[i][j]=1;
  16.              }
  17.          }
  18.      }
  19.  
  20. //Method 2:
  21. //TC O(N*M) space O(1)
  22. //we did same as the method 1 ,we wanted to store the row and col having one at some place,so we will store at
  23. //oth row and oth col and one more thing to find,if 0th row and oth col will be all 1 or not that we did using
  24. //row and col variable and after that traverse the full array and made those (i,j) box 1 whose i is present in
  25. //0th row and whose j is present in 0th col.
  26. //and finally if first row should be 1 then put 1 and same for col.
  27. class Solution
  28. {  
  29.     public:
  30.     //Function to modify the matrix such that if a matrix cell matrix[i][j]
  31.     //is 1 then all the cells in its ith row and jth column will become 1.
  32.     void booleanMatrix(vector<vector<int> > &matrix){
  33.         int row=false,col=false;
  34.         for(int i=0;i<matrix.size();i++){
  35.             for(int j=0;j<matrix[i].size();j++){
  36.                 if(matrix[i][j]==1 && i==0) row=true;  //if i==0,means 1st full row should be 1
  37.                 if(matrix[i][j]==1 && j==0) col=true;  //if j==1,means 1st full col should be 1
  38.                 if(matrix[i][j]==1){                  
  39.                     matrix[0][j]=1;                     //marked the column which should be 1
  40.                     matrix[i][0]=1;                     //marked the row which should be 1
  41.                 }
  42.             }
  43.         }
  44.        
  45.         for(int i=1;i<matrix.size();i++){
  46.             for(int j=1;j<matrix[i].size();j++){
  47.                 if(matrix[i][j]==0 && (matrix[0][j]==1 || matrix[i][0]==1) ) matrix[i][j]=1;
  48.             }
  49.         }
  50.        
  51.         for(int i=0;i<matrix.size();i++){
  52.             for(int j=0;j<matrix[i].size();j++){
  53.                 if(row){
  54.                     matrix[0][j]=1;
  55.                 }
  56.                 if(col){
  57.                     matrix[i][0]=1;
  58.                 }
  59.             }
  60.         }
  61.        
  62.     }
  63. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement