Coin Path
HardUpdated: Jul 7, 2025
Practice on:
Problem
You are given an integer array coins (1-indexed) of length n and an integer maxJump. You can jump to any index i of the array coins if coins[i] != -1 and you have to pay coins[i] when you visit index i. In addition to that, if you are currently at index i, you can only jump to any index i + k where i + k <= n and k is a value in the range [1, maxJump].
You are initially positioned at index 1 (coins[1] is not -1). You want to find the path that reaches index n with the minimum cost.
Return an integer array of the indices that you will visit in order so that you can reach index n with the minimum cost. If there are multiple paths with the same cost, return the lexicographically smallest such path. If it is not possible to reach index n, return an empty array.
A path p1 = [Pa1, Pa2, ..., Pax] of length x is lexicographically smaller than p2 = [Pb1, Pb2, ..., Pbx] of length y, if and only if at the first j where Paj and Pbj differ, Paj < Pbj; when no such j exists, then x < y.
Examples
Example 1:
Input: coins = [1,2,4,-1,2], maxJump = 2
Output: [1,3,5]
Example 2:
Input: coins = [1,2,4,-1,2], maxJump = 1
Output: []
Constraints:
1 <= coins.length <= 1000-1 <= coins[i] <= 100coins[1] != -11 <= maxJump <= 100
Solution
Method 1 – Dynamic Programming with Path Reconstruction
Intuition
Use DP to find the minimum cost to reach each index. For lexicographically smallest path, always update the path if a new minimum is found or if the path is smaller.
Approach
- Let
dp[i]be the minimum cost to reach indexi(1-based). Initializedp[0]=coins[0], others to inf. - For each index
i, try all jumpskin[1, maxJump]toi+kifcoins[i+k] != -1. - If a new minimum is found for
dp[i+k], updatedp[i+k]and record the path. - At the end, reconstruct the path from the recorded previous indices.
- If
dp[n-1]is inf, return empty array.
Complexity
- ⏰ Time complexity:
O(n * maxJump), because for each of thenpositions, we check up tomaxJumpnext positions. - 🧺 Space complexity:
O(n), as we store DP and previous index arrays of sizen.
Code
C++
class Solution {
public:
vector<int> cheapestJump(vector<int>& coins, int maxJump) {
int n = coins.size();
vector<int> dp(n, INT_MAX), prev(n, -1);
dp[0] = coins[0];
for (int i = 0; i < n; ++i) {
if (coins[i] == -1 || dp[i] == INT_MAX) continue;
for (int j = i+1; j <= min(i+maxJump, n-1); ++j) {
if (coins[j] == -1) continue;
int cost = dp[i] + coins[j];
if (cost < dp[j]) {
dp[j] = cost;
prev[j] = i;
} else if (cost == dp[j] && prev[j] > i) {
prev[j] = i;
}
}
}
if (dp[n-1] == INT_MAX) return {};
vector<int> path;
for (int idx = n-1; idx != -1; idx = prev[idx]) path.push_back(idx+1);
reverse(path.begin(), path.end());
return path;
}
};
Go
type Solution struct{}
func (Solution) CheapestJump(coins []int, maxJump int) []int {
n := len(coins)
dp := make([]int, n)
prev := make([]int, n)
for i := range dp { dp[i] = 1<<31-1; prev[i] = -1 }
dp[0] = coins[0]
for i := 0; i < n; i++ {
if coins[i] == -1 || dp[i] == 1<<31-1 { continue }
for j := i+1; j <= i+maxJump && j < n; j++ {
if coins[j] == -1 { continue }
cost := dp[i] + coins[j]
if cost < dp[j] {
dp[j] = cost; prev[j] = i
} else if cost == dp[j] && prev[j] > i {
prev[j] = i
}
}
}
if dp[n-1] == 1<<31-1 { return []int{} }
path := []int{}
for idx := n-1; idx != -1; idx = prev[idx] { path = append([]int{idx+1}, path...) }
return path
}
Java
class Solution {
public List<Integer> cheapestJump(int[] coins, int maxJump) {
int n = coins.length;
int[] dp = new int[n];
int[] prev = new int[n];
Arrays.fill(dp, Integer.MAX_VALUE);
Arrays.fill(prev, -1);
dp[0] = coins[0];
for (int i = 0; i < n; ++i) {
if (coins[i] == -1 || dp[i] == Integer.MAX_VALUE) continue;
for (int j = i+1; j <= Math.min(i+maxJump, n-1); ++j) {
if (coins[j] == -1) continue;
int cost = dp[i] + coins[j];
if (cost < dp[j]) {
dp[j] = cost;
prev[j] = i;
} else if (cost == dp[j] && prev[j] > i) {
prev[j] = i;
}
}
}
if (dp[n-1] == Integer.MAX_VALUE) return new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
for (int idx = n-1; idx != -1; idx = prev[idx]) path.addFirst(idx+1);
return path;
}
}
Kotlin
class Solution {
fun cheapestJump(coins: IntArray, maxJump: Int): List<Int> {
val n = coins.size
val dp = IntArray(n) { Int.MAX_VALUE }
val prev = IntArray(n) { -1 }
dp[0] = coins[0]
for (i in 0 until n) {
if (coins[i] == -1 || dp[i] == Int.MAX_VALUE) continue
for (j in i+1..minOf(i+maxJump, n-1)) {
if (coins[j] == -1) continue
val cost = dp[i] + coins[j]
if (cost < dp[j]) {
dp[j] = cost
prev[j] = i
} else if (cost == dp[j] && prev[j] > i) {
prev[j] = i
}
}
}
if (dp[n-1] == Int.MAX_VALUE) return emptyList()
val path = mutableListOf<Int>()
var idx = n-1
while (idx != -1) {
path.add(idx+1)
idx = prev[idx]
}
return path.reversed()
}
}
Python
class Solution:
def cheapestJump(self, coins: list[int], maxJump: int) -> list[int]:
n = len(coins)
dp = [float('inf')] * n
prev = [-1] * n
dp[0] = coins[0]
for i in range(n):
if coins[i] == -1 or dp[i] == float('inf'):
continue
for j in range(i+1, min(i+maxJump+1, n)):
if coins[j] == -1:
continue
cost = dp[i] + coins[j]
if cost < dp[j]:
dp[j] = cost
prev[j] = i
elif cost == dp[j] and prev[j] > i:
prev[j] = i
if dp[-1] == float('inf'):
return []
path = []
idx = n-1
while idx != -1:
path.append(idx+1)
idx = prev[idx]
return path[::-1]
Rust
impl Solution {
pub fn cheapest_jump(coins: Vec<i32>, max_jump: i32) -> Vec<i32> {
let n = coins.len();
let mut dp = vec![i32::MAX; n];
let mut prev = vec![-1; n];
dp[0] = coins[0];
for i in 0..n {
if coins[i] == -1 || dp[i] == i32::MAX { continue; }
for j in i+1..=std::cmp::min(i+max_jump as usize, n-1) {
if coins[j] == -1 { continue; }
let cost = dp[i] + coins[j];
if cost < dp[j] {
dp[j] = cost;
prev[j] = i as i32;
} else if cost == dp[j] && prev[j] > i as i32 {
prev[j] = i as i32;
}
}
}
if dp[n-1] == i32::MAX { return vec![]; }
let mut path = vec![];
let mut idx = n as i32 - 1;
while idx != -1 {
path.push(idx+1);
idx = prev[idx as usize];
}
path.reverse();
path
}
}
TypeScript
class Solution {
cheapestJump(coins: number[], maxJump: number): number[] {
const n = coins.length;
const dp = Array(n).fill(Number.POSITIVE_INFINITY);
const prev = Array(n).fill(-1);
dp[0] = coins[0];
for (let i = 0; i < n; ++i) {
if (coins[i] === -1 || dp[i] === Number.POSITIVE_INFINITY) continue;
for (let j = i + 1; j <= Math.min(i + maxJump, n - 1); ++j) {
if (coins[j] === -1) continue;
const cost = dp[i] + coins[j];
if (cost < dp[j]) {
dp[j] = cost;
prev[j] = i;
} else if (cost === dp[j] && prev[j] > i) {
prev[j] = i;
}
}
}
if (dp[n - 1] === Number.POSITIVE_INFINITY) return [];
const path: number[] = [];
let idx = n - 1;
while (idx !== -1) {
path.push(idx + 1);
idx = prev[idx];
}
return path.reverse();