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.
- def booleanMatrix_method1(matrix):
- row, col = {}, {}
- for i in range(len(matrix)):
- for j in range(len(matrix[i])):
- if matrix[i][j] == 1:
- row[i] = 1
- col[j] = 1
- for i in range(len(matrix)):
- for j in range(len(matrix[i])):
- if matrix[i][j] == 0 and (row.get(i, 0) or col.get(j, 0)):
- 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:
- #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.
- def booleanMatrix(self, matrix):
- row = False
- col = False
- for i in range(len(matrix)):
- for j in range(len(matrix[i])):
- if matrix[i][j] == 1 and i == 0:
- row = True #if i==0,means 1st full row should be 1
- if matrix[i][j] == 1 and 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 i in range(1, len(matrix)):
- for j in range(1, len(matrix[i])):
- if matrix[i][j] == 0 and (matrix[0][j] == 1 or matrix[i][0] == 1):
- matrix[i][j] = 1
- for i in range(len(matrix)):
- for j in range(len(matrix[i])):
- if row:
- matrix[0][j] = 1
- if col:
- matrix[i][0] = 1
Advertisement
Add Comment
Please, Sign In to add comment