LeetCode 656: Coin Path Solution in Python – A Step-by-Step Guide

What Is LeetCode 656: Coin Path?

In LeetCode 656: Coin Path, you’re given an integer array A of length n and an integer B (max jump distance). Each element A[i] is either a non-negative cost or -1 (blocked). Starting at index 0, you can jump up to B steps forward to an unblocked index, accumulating costs. Your task is to find the cheapest path (minimum total cost) from index 0 to n-1, returning the path as a list of indices (1-based). If multiple paths have the same minimum cost, return the lexicographically smallest one. If no path exists, return an empty list. For example, with A = [1, 2, 4, -1, 2] and B = 2, the path [1, 3, 5] (0-based: [0, 2, 4]) costs 7. This problem tests your ability to optimize paths with constraints.

Problem Statement

• Input:
• A: List of integers (costs or -1 for blocked).
• B: Integer (max jump distance).
• Output: A list of integers—cheapest path (1-based indices), lexicographically smallest if tied.
• Rules:
• Start at index 0, reach n-1.
• Jump 1 to B steps to unblocked indices.
• Minimize total cost; if tied, minimize path lexicographically.
• Return [] if no path exists.

Constraints

• 1 ≤ A.length ≤ 20.
• 1 ≤ B ≤ 10.
• -1 ≤ A[i] < 2³¹.

Examples

• Input: A = [1, 2, 4, -1, 2], B = 2
• Output: [1, 3, 5] (Path: 0→2→4, cost = 1+4+2=7)
• Input: A = [1, 2, 4, -1, 2], B = 1
• Output: [] (No path possible)
• Input: A = [2, 1], B = 2
• Output: [1, 2] (Path: 0→1, cost = 2+1=3)

These examples set the path—let’s solve it!

Understanding the Problem: Finding the Cheapest Path

To solve LeetCode 656: Coin Path in Python, we need to find the cheapest path from index 0 to n-1 in array A, jumping up to B steps, avoiding -1’s, and picking the lexicographically smallest path among ties. A brute-force approach—trying all possible paths—would be O(B^n), exponential and impractical for n ≤ 20. Since costs and jumps form a directed acyclic graph (DAG), we can optimize with DP or greedy strategies. We’ll use:

• Best Solution (Dynamic Programming with Path Tracking): O(n * B) time, O(n) space—fast and optimal.
• Alternative Solution (Greedy with Backtracking): O(n * B) time, O(n) space—simpler but heuristic.

Let’s start with the DP solution, breaking it down for beginners.

Best Solution: Dynamic Programming with Path Tracking

Why This Is the Best Solution

The dynamic programming with path tracking approach is the top choice for LeetCode 656 because it’s efficient—O(n * B) time with O(n) space—and guarantees the cheapest path by computing minimum costs and tracking paths, resolving ties lexicographically in a single pass. It fits constraints (n ≤ 20, B ≤ 10) perfectly and is clear once you see the DP table. It’s like charting the cheapest route step-by-step!

How It Works

Think of this as a path planner:

• Step 1: Initialize DP Arrays:
• dp[i]: Min cost to reach index i from 0.
• path[i]: Previous index in cheapest path to i.
• Base: dp[0] = A[0], others infinity.
• Step 2: Fill DP:
• For each i from 0 to n-1:
• If A[i] ≠ -1, try jumps j (1 to B):
• Update dp[i+j] if cheaper, record i in path[i+j].
• If equal cost, pick smaller i (lexicographical order).
• Step 3: Reconstruct Path:
• If dp[n-1] is infinity, return [].
• Backtrack from n-1 using path to build result.
• Step 4: Return Result:
• Convert to 1-based indices.

It’s like a cost mapper—plan and trace!

Step-by-Step Example

Example: A = [1, 2, 4, -1, 2], B = 2

• Step 1: Init:
• dp = [1, inf, inf, inf, inf].
• path = [-1, -1, -1, -1, -1].
• Step 2: Fill:
• i=0 (1):
• j=1: dp[1] = 1+2=3, path[1] = 0.
• j=2: dp[2] = 1+4=5, path[2] = 0.
• i=1 (2):
• j=1: dp[2] = min(5, 3+4=7), keep 5, path[2] = 0.
• j=2: dp[3] = inf (blocked).
• i=2 (4):
• j=1: dp[3] = inf (blocked).
• j=2: dp[4] = 5+2=7, path[4] = 2.
• i=3 (-1): Skip.
• i=4 (2): Done.
• Step 3: Reconstruct:
• dp[4] = 7, path[4] = 2, path[2] = 0, path[0] = -1.
• Path = [0, 2, 4] → [1, 3, 5].
• Output: [1, 3, 5].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class Solution:
    def cheapestJump(self, A: List[int], B: int) -> List[int]:
        # Step 1: Initialize DP arrays
        n = len(A)
        dp = [float('inf')] * n
        path = [-1] * n
        dp[0] = A[0] if A[0] != -1 else float('inf')

        # Step 2: Fill DP table
        for i in range(n):
            if A[i] == -1 or dp[i] == float('inf'):
                continue
            for j in range(1, min(B + 1, n - i)):
                next_idx = i + j
                if A[next_idx] != -1:
                    new_cost = dp[i] + A[next_idx]
                    # Update if cheaper or equal cost but lexicographically smaller
                    if new_cost < dp[next_idx] or (new_cost == dp[next_idx] and i < path[next_idx]):
                        dp[next_idx] = new_cost
                        path[next_idx] = i

        # Step 3: Reconstruct path
        if dp[n - 1] == float('inf'):
            return []

        result = []
        curr = n - 1
        while curr != -1:
            result.append(curr + 1)  # Convert to 1-based
            curr = path[curr]
        return result[::-1]  # Reverse to get forward path

• Lines 4-8: Init: dp for costs, path for tracking, set dp[0].
• Lines 11-21: Fill:
• Skip blocked or unreachable, try jumps, update dp/path.
• Lines 24-31: Reconstruct:
• Check if reachable, backtrack via path, convert to 1-based.
• Time Complexity: O(n * B)—n positions, B jumps each.
• Space Complexity: O(n)—dp and path arrays.

This is like a path finder—map and trace!

Alternative Solution: Greedy with Backtracking

Why an Alternative Approach?

The greedy with backtracking approach tries to build the cheapest path iteratively—O(n * B) time, O(n) space. It’s simpler, greedily picking the next step, but requires backtracking to ensure lexicographical order, making it less reliable without full optimization. It’s like hopping forward, adjusting if needed!

How It Works

Picture this as a path hopper:

• Step 1: Init path and cost.
• Step 2: Greedy steps:
• From current index, try jumps (1 to B).
• Pick cheapest unblocked, add to path.
• Step 3: Backtrack for lexicographical order:
• If multiple cheapest paths, retry earlier jumps.
• Step 4: Return path or [] if unreachable.

It’s like a greedy jumper—hop and fix!

Step-by-Step Example

Example: Same as above

• Step 1: Path = [1], cost = 1, curr = 0.
• Step 2: Greedy:
• From 0: 1(2), 2(4), pick 2, Path = [1, 3], cost = 5, curr = 2.
• From 2: 1(-1), 2(2), pick 2, Path = [1, 3, 5], cost = 7, curr = 4.
• Step 3: Reached end, no ties to adjust.
• Output: [1, 3, 5].

Code for Greedy Approach

class Solution:
    def cheapestJump(self, A: List[int], B: int) -> List[int]:
        # Step 1: Initialize
        n = len(A)
        if A[0] == -1 or n == 0:
            return []

        # Step 2: Greedy path building
        path = [1]
        curr = 0
        total_cost = A[0]

        while curr < n - 1:
            min_cost = float('inf')
            next_idx = -1
            for j in range(1, min(B + 1, n - curr)):
                if A[curr + j] != -1 and A[curr + j] < min_cost:
                    min_cost = A[curr + j]
                    next_idx = curr + j
            if next_idx == -1:
                return []  # No valid jump
            curr = next_idx
            total_cost += A[curr]
            path.append(curr + 1)

        # Step 3: Return path (no backtracking for simplicity here)
        return path if curr == n - 1 else []

• Lines 4-6: Handle invalid start.
• Lines 9-12: Init: Start path, cost, position.
• Lines 14-24: Greedy:
• Find cheapest next jump, update path/cost.
• Line 27: Return path if end reached.
• Time Complexity: O(n * B)—n steps, B checks each.
• Space Complexity: O(n)—path storage.

It’s a path guesser—jump and hope!

Comparing the Two Solutions

• DP (Best):
• Pros: O(n * B) time, O(n) space, optimal and exact.
• Cons: DP setup more complex.
• Greedy (Alternative):
• Pros: O(n * B) time, O(n) space, simpler logic.
• Cons: May miss lexicographical order without full backtracking.

DP wins for correctness.

Additional Examples and Edge Cases

• Input: A = [1, -1, 2], B = 2
• Output: [].
• Input: A = [1, 1, 1], B = 2
• Output: [1, 2, 3] (lexicographically smallest).

DP handles these precisely.

Complexity Breakdown

• DP: Time O(n * B), Space O(n).
• Greedy: Time O(n * B), Space O(n).

DP is optimal.

Key Takeaways

• DP: Path precision—smart!
• Greedy: Quick hops—clear!
• Paths: Jumping is fun.
• Python Tip: DP rocks—see Python Basics.

Final Thoughts: Find That Path

LeetCode 656: Coin Path in Python is a fun path challenge. DP with path tracking ensures the cheapest, smallest path, while greedy offers a quick heuristic. Want more? Try LeetCode 322: Coin Change or LeetCode 787: Cheapest Flights Within K Stops. Ready to hop? Head to Solve LeetCode 656 on LeetCode and find that path today!