aakarshmadhavan's blog

Tough heap problem
By aakarshmadhavan, history, 6 years 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

»
6 years 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.

→ Reply