LeetCode 656: Coin Path

Problem Restatement

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

The array represents positions from 1 to n.

At position i, we must pay coins[i] coins when we visit that position.

Some positions have value -1. These positions are blocked and cannot be visited.

We start at position 1.

We want to reach position n.

From position i, we may jump forward to any position from:

i + 1

up to:

i + maxJump

Return the path of positions we visit, using 1-based indices.

The path must have minimum total cost. If multiple paths have the same minimum cost, return the lexicographically smallest path. If reaching position n is impossible, return an empty list.

Input and Output

Example function shape:

def cheapestJump(coins: list[int], maxJump: int) -> list[int]:
    ...

Examples

Consider:

coins = [1, 2, 4, -1, 2]
maxJump = 2

The positions are:

From position 1, we can jump to position 2 or 3.

One valid path is:

[1, 3, 5]

Its cost is:

1 + 4 + 2 = 7

Position 4 is blocked, so paths through position 4 are invalid.

The answer is:

[1, 3, 5]

Now consider:

coins = [1, 2, 4, -1, 2]
maxJump = 1

We can only move one step at a time.

The path would need to go through position 4, but position 4 is blocked.

So the answer is:

[]

First Thought: Try Every Path

A direct solution is to try every possible jump sequence from position 1.

At each position, we can jump to up to maxJump next positions.

This creates a branching search tree.

For each path, we compute the total cost. Then we choose the path with the smallest cost. If there is a tie, we choose the lexicographically smallest path.

This is logically correct, but it repeats the same subproblems many times.

For example, many different paths may reach the same position. Once we are at that position, the best way to finish is the same regardless of how we got there.

That repeated structure suggests dynamic programming.

Key Insight

Let dp[i] mean:

minimum cost needed to reach the final position starting from index i

Here, i is a 0-based index into coins.

If coins[i] == -1, then position i is blocked, so dp[i] is impossible.

If i is the last index, then:

dp[i] = coins[i]

because we are already at the destination and only pay the current position cost.

For every other index, we try all next reachable positions:

i + 1, i + 2, ..., i + maxJump

and choose the one with minimum total cost.

The recurrence is:

dp[i] = coins[i] + min(dp[j])

where j ranges over reachable next indices.

Lexicographic Tie-Breaking

The problem also asks for the lexicographically smallest path among all minimum-cost paths.

A path is lexicographically smaller if, at the first different index, it has the smaller position number.

Since we reconstruct the path from left to right, we can enforce this rule by choosing the smallest next index that still gives the optimal cost.

That means when we compute dp[i], if two next positions give the same cost, we prefer the smaller next position.

So we scan next positions in increasing order and update only when we find a strictly smaller cost.

This preserves the earliest possible next position for ties.

Algorithm

Use bottom-up dynamic programming from right to left.

Create:

Initialize:

dp[n - 1] = coins[n - 1]

Then process indices from n - 2 down to 0.

For each index i:

1. If coins[i] == -1, skip it.
2. Try every j from i + 1 to min(i + maxJump, n - 1).
3. Ignore j if dp[j] is impossible.
4. Compute cost = coins[i] + dp[j].
5. If cost is smaller than dp[i], update dp[i] and next_index[i].
6. Do not update on equal cost, because the earlier j is lexicographically better.

After filling DP:

1. If dp[0] is impossible, return [].
2. Otherwise, follow next_index from 0 to n - 1.
3. Convert each index to 1-based form.

Correctness

The value dp[i] represents the minimum cost to reach the last position starting from index i.

For the last index, this is exactly coins[i], because we are already at the destination.

For every other usable index i, any valid path must jump next to some index j within maxJump steps. After that jump, the best possible remaining cost is dp[j]. Therefore, the best cost from i is coins[i] + min(dp[j]) over all valid next positions.

The algorithm computes states from right to left, so when it computes dp[i], every reachable dp[j] has already been computed.

The next_index array stores a next position that achieves the minimum cost. Since candidates are checked from smaller index to larger index and equal-cost updates are ignored, the stored next position is the smallest possible next index among all optimal choices.

During reconstruction, the algorithm repeatedly chooses the smallest next index that can still lead to an optimal path. Therefore, among all minimum-cost paths, the constructed path is lexicographically smallest.

If dp[0] remains impossible, no valid sequence of jumps can reach the last position from the start, so returning an empty list is correct.

Complexity

Implementation

from math import inf
from typing import List

class Solution:
    def cheapestJump(self, coins: List[int], maxJump: int) -> List[int]:
        n = len(coins)

        if n == 0 or coins[0] == -1 or coins[-1] == -1:
            return []

        dp = [inf] * n
        next_index = [-1] * n

        dp[n - 1] = coins[n - 1]

        for i in range(n - 2, -1, -1):
            if coins[i] == -1:
                continue

            limit = min(n - 1, i + maxJump)

            for j in range(i + 1, limit + 1):
                if dp[j] == inf:
                    continue

                cost = coins[i] + dp[j]

                if cost < dp[i]:
                    dp[i] = cost
                    next_index[i] = j

        if dp[0] == inf:
            return []

        path = []
        i = 0

        while i != -1:
            path.append(i + 1)

            if i == n - 1:
                break

            i = next_index[i]

        return path

Code Explanation

We first reject impossible start or end positions:

if n == 0 or coins[0] == -1 or coins[-1] == -1:
    return []

Then we create the DP arrays:

dp = [inf] * n
next_index = [-1] * n

inf means the end cannot be reached from that index yet.

The destination cost is initialized directly:

dp[n - 1] = coins[n - 1]

Then we process from right to left:

for i in range(n - 2, -1, -1):

Blocked positions are skipped:

if coins[i] == -1:
    continue

For a valid position, we try all jumps within range:

limit = min(n - 1, i + maxJump)

for j in range(i + 1, limit + 1):

If j cannot reach the end, we ignore it:

if dp[j] == inf:
    continue

Otherwise, we compute the total cost through j:

cost = coins[i] + dp[j]

We update only on strictly smaller cost:

if cost < dp[i]:
    dp[i] = cost
    next_index[i] = j

This is important for lexicographic order. Since j is scanned from left to right, the first minimum-cost j is the smallest valid next position.

After DP finishes, we check whether index 0 can reach the end:

if dp[0] == inf:
    return []

Finally, we reconstruct the path:

path = []
i = 0

while i != -1:
    path.append(i + 1)

    if i == n - 1:
        break

    i = next_index[i]

We append i + 1 because the problem asks for 1-based indices.

Testing

def run_tests():
    s = Solution()

    assert s.cheapestJump([1, 2, 4, -1, 2], 2) == [1, 3, 5]
    assert s.cheapestJump([1, 2, 4, -1, 2], 1) == []

    # Direct jump is possible and cheapest.
    assert s.cheapestJump([1, 10, 10, 1], 3) == [1, 4]

    # Tie on total cost. Choose lexicographically smaller path.
    assert s.cheapestJump([1, 1, 1, 1], 2) == [1, 2, 4]

    # Blocked cells force a longer route.
    assert s.cheapestJump([1, -1, 2, 2, 1], 2) == [1, 3, 5]

    # Destination blocked.
    assert s.cheapestJump([1, 2, -1], 2) == []

    print("all tests passed")

run_tests()

Test meaning: