LeetCode 656 - Coin Path

This problem asks us to find the cheapest valid path through an array while respecting jump constraints and blocked positions. The array coins is 1-indexed in the problem statement, although programming languages will use 0-indexed arrays internally.

leetcodehardarraydynamic-programming

LeetCode Problem 656

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

This problem asks us to find the cheapest valid path through an array while respecting jump constraints and blocked positions.

The array coins is 1-indexed in the problem statement, although programming languages will use 0-indexed arrays internally. Each position contains either:

  • A non-negative integer representing the cost of landing on that index
  • -1, meaning the position is blocked and cannot be visited

You start at index 1 and must reach index n. From any current position i, you may jump forward to any position i + k where:

  • 1 <= k <= maxJump
  • i + k <= n
  • The destination position is not blocked

Whenever you land on a position, you pay its coin cost. The goal is to minimize the total cost of the path.

The output is not the minimum cost itself. Instead, we must return the sequence of indices visited along the optimal path.

An additional complication is the lexicographical ordering requirement. If multiple paths have the same minimum total cost, we must return the lexicographically smallest one.

For example:

  • [1,2,5] is lexicographically smaller than [1,3,4] because at the first differing position, 2 < 3
  • [1,2] is lexicographically smaller than [1,2,3] because the shorter sequence wins when one is a prefix of the other

The constraints are relatively small:

  • n <= 1000
  • maxJump <= 100

These constraints strongly suggest that an O(n * maxJump) dynamic programming solution is appropriate.

Several important edge cases appear immediately:

  • The destination may be unreachable
  • Intermediate positions may all be blocked
  • Multiple minimum-cost paths may exist
  • maxJump may be too small to bypass blocked cells
  • The array may contain only one element
  • Large stretches of -1 values may force careful path validation

The problem guarantees that the starting position is always valid, meaning coins[1] != -1.

Approaches

Brute Force Approach

A brute force solution would recursively explore every possible path from index 1 to index n.

At each position, we would try every valid jump from 1 to maxJump, recursively compute all reachable paths, and track:

  • The minimum total cost
  • The lexicographically smallest path among ties

This approach is correct because it exhaustively enumerates every valid path and directly compares them according to the problem rules.

However, the number of possible paths grows exponentially. At each position we may branch into as many as maxJump choices, leading to an enormous search tree. Even with memoization, comparing entire paths repeatedly becomes expensive.

For n = 1000, brute force is completely impractical.

Optimal Dynamic Programming Approach

The key observation is that the cheapest path to a position depends only on the cheapest paths to earlier reachable positions.

This naturally leads to dynamic programming.

We define:

  • dp[i] = minimum cost to reach index i
  • parent[i] = previous index used to reach i optimally

We compute the solution backward from the end of the array toward the beginning.

Why backward DP works especially well here:

  • From position i, we choose the best next jump
  • We already know the optimal solution for later positions
  • Lexicographical ordering becomes easier to handle

When multiple next positions produce the same cost, we choose the smaller next index. Because paths are built forward, choosing the smaller next step guarantees lexicographically smaller results.

This gives an efficient O(n * maxJump) solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(maxJump^n) O(n) Explores every possible path recursively
Optimal O(n * maxJump) O(n) Dynamic programming with path reconstruction

Algorithm Walkthrough

Step 1: Initialize DP Arrays

We create two arrays:

  • dp[i] stores the minimum cost required to reach the end starting from index i
  • next_index[i] stores the next position chosen from i

Initially:

  • All values are infinity because we assume positions are unreachable
  • The destination position gets initialized specially

If the last position is not blocked:

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

This means the cost to finish from the last index is simply its own coin value.

Step 2: Process Positions Backward

We iterate from n-2 down to 0.

Backward traversal is important because when evaluating jumps from i, we already know the optimal future costs for all reachable destinations.

For each position:

  • Skip it if coins[i] == -1
  • Otherwise examine every jump length from 1 to maxJump

Step 3: Evaluate Reachable Next Positions

For every reachable position j:

  • Ignore blocked or unreachable positions
  • Compute candidate cost:
coins[i] + dp[j]

If this cost is smaller than the current best:

  • Update dp[i]
  • Record next_index[i] = j

Step 4: Handle Lexicographical Tie Breaking

If two choices produce the same total cost:

  • Choose the smaller next index

Because paths are reconstructed greedily forward, selecting the smaller immediate next step guarantees lexicographically smaller paths overall.

Step 5: Check Reachability

After DP finishes:

  • If dp[0] is still infinity, no valid path exists
  • Return an empty array

Step 6: Reconstruct the Path

Starting from index 0:

  • Append current position to the answer
  • Move to next_index[current]
  • Continue until reaching the destination

Remember to convert indices back to 1-indexed format before returning.

Why it works

The dynamic programming state guarantees that dp[i] always stores the minimum possible cost from position i to the end.

Because positions are processed backward, every future state has already been computed optimally before it is used.

The lexicographical rule is satisfied because when costs tie, the algorithm always chooses the smallest possible next index. Since lexicographical comparison depends on the earliest differing element, this greedy tie-breaking strategy produces the lexicographically smallest optimal path.

Python Solution

from typing import List

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

        INF = float("inf")

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

        if coins[n - 1] != -1:
            dp[n - 1] = coins[n - 1]

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

            for j in range(i + 1, min(n, i + maxJump + 1)):
                if dp[j] == INF:
                    continue

                candidate_cost = coins[i] + dp[j]

                if candidate_cost < dp[i]:
                    dp[i] = candidate_cost
                    next_index[i] = j
                elif (
                    candidate_cost == dp[i]
                    and (next_index[i] == -1 or j < next_index[i])
                ):
                    next_index[i] = j

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

        path = []
        current = 0

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

            if current == n - 1:
                break

            current = next_index[current]

        return path

The implementation begins by initializing the DP and parent-tracking arrays.

dp[i] stores the minimum cost from index i to the destination. Every value begins as infinity to represent unreachable states.

next_index[i] records which next jump produces the optimal path.

The destination index is initialized first because its cost is already known directly.

The main DP loop processes indices backward. For each valid position, the algorithm checks every legal jump destination within maxJump.

Whenever a cheaper path is found, the DP value and next pointer are updated.

If two candidate paths have identical cost, the algorithm chooses the smaller next index to preserve lexicographical ordering.

Finally, the path is reconstructed by repeatedly following next_index pointers from the start until reaching the destination.

Go Solution

package main

import "math"

func cheapestJump(coins []int, maxJump int) []int {
	n := len(coins)

	const INF = math.MaxInt32

	dp := make([]int, n)
	nextIndex := make([]int, n)

	for i := 0; i < n; i++ {
		dp[i] = INF
		nextIndex[i] = -1
	}

	if coins[n-1] != -1 {
		dp[n-1] = coins[n-1]
	}

	for i := n - 2; i >= 0; i-- {
		if coins[i] == -1 {
			continue
		}

		end := i + maxJump
		if end >= n {
			end = n - 1
		}

		for j := i + 1; j <= end; j++ {
			if dp[j] == INF {
				continue
			}

			candidateCost := coins[i] + dp[j]

			if candidateCost < dp[i] {
				dp[i] = candidateCost
				nextIndex[i] = j
			} else if candidateCost == dp[i] &&
				(nextIndex[i] == -1 || j < nextIndex[i]) {
				nextIndex[i] = j
			}
		}
	}

	if dp[0] == INF {
		return []int{}
	}

	result := []int{}
	current := 0

	for current != -1 {
		result = append(result, current+1)

		if current == n-1 {
			break
		}

		current = nextIndex[current]
	}

	return result
}

The Go implementation closely mirrors the Python version.

One important difference is the handling of infinity. Go does not provide a direct integer infinity value, so math.MaxInt32 is used as a sufficiently large sentinel.

Slices are used for dynamic arrays, and an empty slice []int{} is returned when no path exists.

Go also requires explicit bounds handling when computing jump ranges.

Worked Examples

Example 1

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

We use 0-indexed internal representation.

Initial state:

Index Coin dp next
0 1 INF -1
1 2 INF -1
2 4 INF -1
3 -1 INF -1
4 2 2 -1

Process index 3:

  • Blocked, skip

Process index 2:

Possible jump:

  • 4

Cost:

  • 4 + 2 = 6

Update:

Index dp next
2 6 4

Process index 1:

Possible jumps:

  • 2 → cost 2 + 6 = 8
  • 3 blocked

Update:

Index dp next
1 8 2

Process index 0:

Possible jumps:

  • 1 → cost 1 + 8 = 9
  • 2 → cost 1 + 6 = 7

Choose index 2 because cost is smaller.

Final DP:

Index dp next
0 7 2
1 8 2
2 6 4
3 INF -1
4 2 -1

Reconstruction:

  • 0 → 2 → 4

Convert to 1-indexed:

[1,3,5]

Example 2

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

Only adjacent jumps are allowed.

Position 3 is blocked, so position 4 cannot be reached.

DP never finds a valid route to the end.

Final result:

[]

Complexity Analysis

Measure Complexity Explanation
Time O(n * maxJump) Each index examines at most maxJump future positions
Space O(n) DP and parent arrays each store n elements

The algorithm processes every index once, and for each index checks up to maxJump possible jumps.

Since maxJump <= 100, the solution is efficient even at the maximum input size.

The auxiliary memory usage is linear because only two arrays of size n are maintained.

Test Cases

from typing import List

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

        INF = float("inf")

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

        if coins[n - 1] != -1:
            dp[n - 1] = coins[n - 1]

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

            for j in range(i + 1, min(n, i + maxJump + 1)):
                if dp[j] == INF:
                    continue

                candidate_cost = coins[i] + dp[j]

                if candidate_cost < dp[i]:
                    dp[i] = candidate_cost
                    next_index[i] = j
                elif (
                    candidate_cost == dp[i]
                    and (next_index[i] == -1 or j < next_index[i])
                ):
                    next_index[i] = j

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

        path = []
        current = 0

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

            if current == n - 1:
                break

            current = next_index[current]

        return path

sol = Solution()

assert sol.cheapestJump([1,2,4,-1,2], 2) == [1,3,5]  # provided example
assert sol.cheapestJump([1,2,4,-1,2], 1) == []  # unreachable destination
assert sol.cheapestJump([1], 1) == [1]  # single element array
assert sol.cheapestJump([1,1,1,1], 2) == [1,2,4]  # lexicographically smallest tie
assert sol.cheapestJump([0,0,0,0], 3) == [1,2,4]  # multiple equal-cost paths
assert sol.cheapestJump([1,-1,-1,1], 2) == []  # blocked middle positions
assert sol.cheapestJump([1,2,3,4,5], 10) == [1,5]  # direct jump to end
assert sol.cheapestJump([1,-1,2,2,1], 2) == [1,3,5]  # jumping over blocked cell
assert sol.cheapestJump([1,1,-1,1,1], 2) == [1,2,4,5]  # forced routing
assert sol.cheapestJump([1,100,1,1,1], 2) == [1,3,5]  # avoid expensive path
Test Why
[1,2,4,-1,2], 2 Validates the provided example
[1,2,4,-1,2], 1 Confirms unreachable detection
[1], 1 Tests smallest possible input
[1,1,1,1], 2 Validates lexicographical tie-breaking
[0,0,0,0], 3 Tests multiple equal-cost paths
[1,-1,-1,1], 2 Ensures blocked paths are handled
[1,2,3,4,5], 10 Tests large jump capability
[1,-1,2,2,1], 2 Verifies jumping over blocked cells
[1,1,-1,1,1], 2 Tests forced detour behavior
[1,100,1,1,1], 2 Confirms cost optimization

Edge Cases

One important edge case occurs when the destination is unreachable. This can happen because of blocked positions or insufficient jump distance. A buggy implementation might still attempt path reconstruction or return a partial path. The DP approach avoids this by checking whether dp[0] remains infinity after computation. If it does, the algorithm immediately returns an empty array.

Another subtle edge case involves lexicographical ordering. Multiple paths may produce the same minimum total cost. If tie-breaking is not handled carefully, the algorithm may return a valid minimum-cost path but not the lexicographically smallest one. This implementation resolves ties by always choosing the smaller next index during DP transitions.

A third important edge case is the single-element array. If coins contains only one value, the start is already the destination. The algorithm correctly initializes the destination cost and reconstructs the path as [1] without requiring any jumps.

Blocked intermediate positions are also a common source of bugs. The algorithm carefully skips any index where coins[i] == -1, both during DP computation and while considering jump destinations. This guarantees that invalid positions are never included in the path.

Finally, large jump ranges can expose off-by-one errors. The implementation carefully bounds the jump range using min(n, i + maxJump + 1) in Python and explicit range limiting in Go, ensuring no out-of-bounds access occurs.