You are given an integer array coins and an integer maxJump.

You start at index $1$ and want to reach index coins.length. From any index $i$, you are allowed to jump to any index $j$ such that $i < j \leq i +$ maxJump and coins[j] $\neq -1$. The cost of jumping to index $j$ is coins[j] coins.

Return the path of $1$ based indices from index $1$ to index coins.length that incurs the minimum total cost. If there are multiple paths with the same minimum cost, return the lexicographically smallest path. If it is impossible to reach the final index, return an empty array.

Constraints:

• $1 \leq$ coins.length $\leq 1000$

• $-1 \leq$ coins[i] $\leq 100$

• coins[1] $\neq -1$

• $1 \leq$ maxJump $\leq 100$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.