aakarshmadhavan's blog

By aakarshmadhavan, history, 4 weeks ago, In English,

Can someone give some hints? I have absolutely no clue how heap or anything else fits into this? Thank you!

 
 
 
 
  • Vote: I like it  
  • -17
  • Vote: I do not like it  

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

I'm not completely sure, but this approach should work — binary search on the final answer.

Assume the answer is <=x. Now, mark arr[i][j]=1 if grid[i][j]<=x and 0 otherwise. Build connected components of 1's in arr. Now the answer is <=x if both the source and destination are 1 and lie in the same connected component of arr. Binary search on x to get your answer.