Click here to see the full article post
Since A1 >= 0. A2, ..., AN (if exist) will in the range of [-1, 100], so A[i]>=0, right?
Try the input below for the last approach:
The output is empty, which is totally wrong.
@zestypanda I have changed it to O(n^2). Thanks.
@vinod23 Thanks. looks good.
Why second approach has O(n^2) time complexity instead of O(nB)? It looks to me that for every node you try at most B possible locations to jump at, which should yield to O(nB) time complexity. And also I think DP and recursive+memorization should have the same time complexity, these two are different ways of coding, in my opinion. Please correct me if I'm wrong.
@KnightY you are right. Thanks for catching that. I have corrected it.
There's also a linear solution using a sliding window.
You need a queue that allows you these operations: push(), pop() and getMin(). This can be done in amortized O(1) time.
Sample accepted implementation: https://gist.github.com/andmej/0832b2677e8c7ccddea84d6a9721f35a
This can be solved a bit better using the Dijkstra path-finding. Go back from finish (for lexicographical ordering) and only explore the cheapest total paths.
It helps in cases like the following:
My solution will only process 5 indices here.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.