Coin Path




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.


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 pathfinding. 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.