# Coin Path

• Since A1 >= 0. A2, ..., AN (if exist) will in the range of [-1, 100], so A[i]>=0, right?

• long cost should be equal to :- A[i] + jump(A, B, j, next), isn't it?

• For the second approach, do you mean the run time is O(n^2) or O(n)?

• The code in the last approach can't pass.

• Try the input below for the last approach:
[0,0,0,0,0,0]
3
The output is empty, which is totally wrong.

• Need to update the code to A[j] >= 0 in all places.

• @zestypanda I have changed it to O(n^2). Thanks.

• @nlharish @kk636 @kk636 @bnslakk I have fixed the codes. Please have a look. 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:
[1,9,9,9,9,9,9,9,9,9,1,9,9,9,9,9,9,9,9,9,1,9,9,9,9,9,9,9,9,9,1,9,9,9,9,9,9,9,9,9,1,9,9,9,9,9,9,9,9,9,1]
10
My solution will only process 5 indices here.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.