Boolean Matrix Problem GFG

#1

https://practice.geeksforgeeks.org/problems/boolean-matrix-problem/0

accepted in leetcode and interviewbit… but gives TLE here. how to optimize?

#2

hello @chaman9

let think of cell (i,j)

in output cell (i,j) will 1 if in input there exist one either in row i or in column j right?.

so the idea is to take two array .row[num of rows] ,col[num of columns]

read input . if input[i][j] is 1. then mark row[i]=1 and col[j]=1
this tells that ok we have 1 in row i. and col j.

now while printing matrix check if row[i]=1 or col[j]=1 then print 1 otherwise 0

#3

hi @aman212yadav, thank you… this approach worked. Can you tell me why ?

the same i did with set it was showing TLE and with array it got accepted

what will be sapce and time complexity in both cases?

#4

in worst CASE insertion in unordered set can be O(N).

here it can be O(N*M) becasue of 2d matrix. may be thats why u r getting tle.

whereas array has constant access time always O(1)

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.