Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Methodd 1:TC = O(N*M) and space complexity O(N+M)
- //LOGIC:we sill store all the rows in map which have 1 atleast one and same for col.
- //after that traverse the matrix,make the (i,j) box=1 if i is in row map,or j is in col map.
- void booleanMatrix(vector<vector<int> > &matrix)
- {
- unordered_map<int,int> row,col;
- for(int i=0;i<matrix.size();i++){
- for(int j=0;j<matrix[i].size();j++){
- if(matrix[i][j]==1){row[i]=1;col[j]=1;}
- }
- }
- for(int i=0;i<matrix.size();i++){
- for(int j=0;j<matrix[i].size();j++){
- if(matrix[i][j]==0 && (row[i] || col[j])) matrix[i][j]=1;
- }
- }
- }
- //Method 2:
- //TC O(N*M) space O(1)
- //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
- //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
- //row and col variable and after that traverse the full array and made those (i,j) box 1 whose i is present in
- //0th row and whose j is present in 0th col.
- //and finally if first row should be 1 then put 1 and same for col.
- class Solution
- {
- public:
- //Function to modify the matrix such that if a matrix cell matrix[i][j]
- //is 1 then all the cells in its ith row and jth column will become 1.
- void booleanMatrix(vector<vector<int> > &matrix){
- int row=false,col=false;
- for(int i=0;i<matrix.size();i++){
- for(int j=0;j<matrix[i].size();j++){
- if(matrix[i][j]==1 && i==0) row=true; //if i==0,means 1st full row should be 1
- if(matrix[i][j]==1 && j==0) col=true; //if j==1,means 1st full col should be 1
- if(matrix[i][j]==1){
- matrix[0][j]=1; //marked the column which should be 1
- matrix[i][0]=1; //marked the row which should be 1
- }
- }
- }
- for(int i=1;i<matrix.size();i++){
- for(int j=1;j<matrix[i].size();j++){
- if(matrix[i][j]==0 && (matrix[0][j]==1 || matrix[i][0]==1) ) matrix[i][j]=1;
- }
- }
- for(int i=0;i<matrix.size();i++){
- for(int j=0;j<matrix[i].size();j++){
- if(row){
- matrix[0][j]=1;
- }
- if(col){
- matrix[i][0]=1;
- }
- }
- }
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement