Bridges 1D DP LIS

#1

I am able to implement it in O(N^2) by LIS standard approach. Is it possible to implement in O(nlogn)?

#2

Hey @pangatt4 as far as i know this problem will only be done using LIS approach, though you can discuss it in with your peers but as far as my domain i don’t have any other approach for doing this problem.

#3

Yes, we have a section on LIS in DP master courser where we solve LIS in O(n logn). And this problem is also an implementation of LIS, so is it possible?

#4

As i know only this approach and it’s O(N^2) as you can see .Though it also gets accepted so there won’t be any optimized solution for this problem. I would suggest you to try it once , you might get succed in solving this in O(NlogN)

1 Like
#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.