# Use PriorityQueue, O(n*lg(B)) (???)

• Let `next[i]` be the index of the optimal step from `A[i]`. We find next[i] backwards - that is to scan from A[n-1] to A[0].

Use `PriorityQueue<int[2]> pq` to keep the cheapest total steps found so far (from `A[i+1]` to `A[i+B]`, technically, `pq` could hold element from index larger than i+B, but we will discard them before peek the min value). Each element `x` in `pq` is `int[2]` type - `x[1]` is the index in A; `x[0]` is the optimal total steps from `A[x[1]]` to `A[n-1]`.

A few notes:

1. if `pq` is emtpy, we can safely terminate the process;
2. the runtime looks like `O(n*lg(B))` to me, but I'm not 100% sure.
``````    public List<Integer> cheapestJump1(int[] A, int B) {
int n = A.length;
int[] next = new int[n];

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));

List<Integer> ans = new ArrayList<>();
pq.add(new int[]{0, n - 1 + B});
for (int i = n - 1; i >= 0; i--) {
if (A[i] == -1) continue;
while (pq.size() > 0 && pq.peek()[1] > i + B)
pq.poll();
if (pq.size() == 0) return ans;
int[] min = pq.peek();
pq.add(new int[]{A[i] + min[0], i});
next[i] = min[1];
}

int i = 0;
do {