Min Jumps

You are given an array of N integers, A₁, A₂ ,…, A_N and an integer B which denotes that from any index i, you can jump to any of the indices i+1, i+2, …, i+B. Also, if you step on index i, you have to pay A_i coins. If A_i is -1, it means you can’t land on index i.

You start from index 1, and your aim is to reach index N. Return the path you should take to minimise the number of coins required. If there are multiple paths with same cost, return the lexicographically smallest such path. If its not possible to reach index N return empty array.

Notes

• A_i is either > 0(denoting cost) or -1(denoting that it is not possible to land on index i).
• You have to pay coins both at starting and ending indices.
• Path a₁, a₂ ,…, a_n is lexicographically smaller than b₁, b₂ ,…, b_m, if and only if at the first i where a_i and b_i differ, a_i < b_i, or if no such i exists, then n < m.

For example,

A=[1, 2, 4, -1, 2] and B = 2

The path which requires minimum coins is to start at index 1 and then move to index 3 and then to 5.
So return [1, 3, 5].

Another example,

A=[1, 2, 4, -1, 2] and B = 1

In this case it is not possible to reach index 5. So return empty array [].

NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a question? Checkout Sample Codes for more details.