Getting TLE on submission in some test cases

#1

this is the link for the code that I submitted.
Could you help me optimize this code futhermore

#2

@sankalp.sharma99
For optimizing what you can do, apply DFS on the matrix and store in a separate array[][], that to which this (i,j) belongs to like start giving some ids randomly that can be like 1,2,3,4…
It actually means that just assign some value(id) to every group of 1’s we have.

So while doing the DFS also store the component size for every ids.

So atlast just traverse the matrix again, for every (i,j) where mat[i][j]=0, find the ids for all the neighbours (here point is the ids can be same or different for neoghbours). So after you have all the distinct ids to which neighbours belong for that (i,j).
Then Just calculate sum of component size for distinct ids and add 1 to it for including current (i,j).
Then just need to take max for (i,j) like this.

#3

If you look at the code , you’ll see that is what I’ve done already.
when finally using the distinct id’s to calculate sum maximum value I’ve used sets. is there any better way to check for distinct id’s?

1 Like
#4

@sankalp.sharma99 ohh ya, you are doing the same thing, but you are using all neighbours of other (i,j) also for current (i,j).
So you just have to clear() the set also for every (i,j).

I hope you got it.

1 Like