We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Coin Path

Number: 656

Difficulty: Hard

Paid? Yes

Companies: Google

Problem Description

Given a 1-indexed array of coins where each element represents a cost (or -1 if unreachable) and a maxJump value, the task is to find a path from index 1 to index n that minimizes the total cost. You can move from index i to any index j in the range [i+1, i+maxJump] provided coins[j] ≠ -1. In case of multiple paths with the same minimum cost, the lexicographically smallest path must be returned.

Key Insights

  • Use dynamic programming (DP) where dp[i] stores both the minimum cost from index i to the end and the corresponding path.
  • Process the indices backward, starting from the last index, to build up a solution from already solved subproblems.
  • For each index, consider all valid jumps within the range of maxJump.
  • When updating dp[i], compare not only the cost but also the lexicographical order of the path in case of cost ties.
  • Carefully handle cases where an index is unreachable (coins[i] == -1) or no subsequent path exists.

Space and Time Complexity

Time Complexity: O(n * maxJump * n) in the worst-case due to the comparisons of path lists while updating dp (where n is the number of coins). Space Complexity: O(n * n) in the worst-case when storing full paths for each dp state.

Solution

The algorithm uses dynamic programming by defining a state dp[i] storing a tuple (min_cost, path) starting at index i. We compute these states in reverse order. For each index i, if the coin is valid (not -1), we iterate over all possible jumps (from 1 to maxJump) and update dp[i] with the best candidate from dp[i+j]. The candidate is chosen first based on the total cost and, if costs are equal, by lexicographical order of the path. Finally, we output the path stored in dp[1] (or dp[0] in 0-indexed implementations). Data structures include arrays (or lists) for dp and vectors or lists for storing paths.

Code Solutions

def coinPath(coins, maxJump):
    n = len(coins)
    # dp[i] stores tuple: (min_cost, path) for 1-indexed position i.
    dp = [None] * (n + 1)
    # Base case: last index
    dp[n] = (coins[n-1], [n]) if coins[n-1] != -1 else None

    # Process indices in reverse order from n-1 down to 1
    for i in range(n-1, 0, -1):
        if coins[i-1] == -1:
            dp[i] = None
            continue
        best = None
        # Try every jump from 1 to maxJump
        for jump in range(1, maxJump+1):
            next_index = i + jump
            if next_index > n or dp[next_index] is None:
                continue
            next_cost, next_path = dp[next_index]
            total_cost = coins[i-1] + next_cost
            candidate = (total_cost, [i] + next_path)
            if best is None:
                best = candidate
            else:
                # Choose candidate with lower cost or lexicographically smaller path if equal cost
                if candidate[0] < best[0]:
                    best = candidate
                elif candidate[0] == best[0] and candidate[1] < best[1]:
                    best = candidate
        dp[i] = best
    return dp[1][1] if dp[1] is not None else []

# Example usage:
print(coinPath([1,2,4,-1,2], 2))  # Output: [1,3,5]
print(coinPath([1,2,4,-1,2], 1))  # Output: []
← Back to All Questions