Coding

Coin Path

Asked at

Amazon

PhonePe

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

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

Input: coins = [2,4,-1,4,3], maxJump = 2 Output: [1,2,4,5]

Input: coins = [4,2,4,-1,5], maxJump = 1 Output: []

Input: coins = [3,4,6,-1,5,3],** maxJump = 2**

1 <= coins.length <= 1000
-1 <= coins[i] <= 100
coins[1] != -1
1 <= maxJump <= 100

cpp

class Solution {
public:
    vector<int> cheapestJump(vector<int>& coins, int maxJump) {
        // User Code goes here
    }
};

java

class Solution {
    public List<Integer> cheapestJump(int[] coins, int maxJump) {
        // User code goes here
    }
}

python

class Solution:
    def cheapestJump(self, coins, maxJump):
        # User Code goes here

javascript

class Solution {
    cheapestJump(coins, maxJump) {
        // User code goes here
    }
}

csharp

public class Solution {
    public List<int> CheapestJump(List<int> coins, int maxJump) {
        // User Code goes here
    }
}

func cheapestJump(coins []int, maxJump int) []int {
// User Code goes here
}

Stuck? Show a way to structure it+

01Compute the cheapest cost from each index to the destination, working backward.
02For each reachable index, inspect the next maxJump positions in ascending order.
03Store the chosen next index and preserve the first candidate on equal cost for lexicographic order.
04Reconstruct from index one or return empty if the destination is unreachable.

Reference answer

Let dp[i] be the minimum total cost of a path beginning at index i and ending at n, including the cost at i. Initialize dp[n] = coins[n] when the destination is usable, and process indices backward. For each usable i, examine reachable j from i + 1 through min(n, i + maxJump). If j is reachable, consider coins[i] + dp[j]. Store the smallest cost and a next[i] pointer. Iterate j in ascending order and replace the choice only for a strictly smaller cost; on ties, the smaller next index remains, producing the lexicographically smallest path because the first differing path position decides the order. If dp[1] remains infinity, return empty. Otherwise follow next pointers to build the path. Time is O(n * maxJump), with O(n) space.

Then expect these follow-ups

Why does choosing the smaller next index settle an equal-cost lexicographic tie?
Tests: tie proof
Can the transition be optimized when maxJump is very large?
Tests: optimization

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question