imashutosh51

Modify Boolean Matrix

Jul 23rd, 2022 (edited)
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.30 KB | None | 0 0
  1. #Methodd 1:TC = O(N*M) and space complexity O(N+M)
  2. #LOGIC:we sill store all the rows in map which have 1 atleast one and same for col.
  3. #after that traverse the matrix,make the (i,j) box=1 if i is in row map,or j is in col map.
  4. def booleanMatrix_method1(matrix):
  5.     row, col = {}, {}
  6.     for i in range(len(matrix)):
  7.         for j in range(len(matrix[i])):
  8.             if matrix[i][j] == 1:
  9.                 row[i] = 1
  10.                 col[j] = 1
  11.  
  12.     for i in range(len(matrix)):
  13.         for j in range(len(matrix[i])):
  14.             if matrix[i][j] == 0 and (row.get(i, 0) or col.get(j, 0)):
  15.                 matrix[i][j] = 1
  16.  
  17.  
  18. #Method 2:
  19. #TC O(N*M) space O(1)
  20. #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
  21. #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
  22. #row and col variable and after that traverse the full array and made those (i,j) box 1 whose i is present in
  23. #0th row and whose j is present in 0th col.
  24. #and finally if first row should be 1 then put 1 and same for col.
  25. class Solution:
  26.     #Function to modify the matrix such that if a matrix cell matrix[i][j]
  27.     #is 1 then all the cells in its ith row and jth column will become 1.
  28.     def booleanMatrix(self, matrix):
  29.         row = False
  30.         col = False
  31.  
  32.         for i in range(len(matrix)):
  33.             for j in range(len(matrix[i])):
  34.                 if matrix[i][j] == 1 and i == 0:
  35.                     row = True  #if i==0,means 1st full row should be 1
  36.                 if matrix[i][j] == 1 and j == 0:
  37.                     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.         for i in range(1, len(matrix)):
  43.             for j in range(1, len(matrix[i])):
  44.                 if matrix[i][j] == 0 and (matrix[0][j] == 1 or matrix[i][0] == 1):
  45.                     matrix[i][j] = 1
  46.  
  47.         for i in range(len(matrix)):
  48.             for j in range(len(matrix[i])):
  49.                 if row:
  50.                     matrix[0][j] = 1
  51.                 if col:
  52.                     matrix[i][0] = 1
  53.  
Advertisement
Add Comment
Please, Sign In to add comment