LeetCode 656: Coin Path Solution

Master LeetCode problem 656 (Coin Path), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

656. Coin Path

Hard

Array Dynamic Programming

Problem Explanation

Explanation

The problem asks to find the minimum path from the first element to the last element of an array where each element represents the value of a coin at that position. The condition is that the path should start from the first element, end at the last element, and at each step, the maximum distance that can be covered is given by the value of the coin at that position.

To solve this problem, we can use dynamic programming. We will iterate through the array from the end to the start, calculating the minimum cost needed to reach the end from each position. We will use an array dp to store the minimum cost at each position. Additionally, we will use a separate array path to store the path from the current position to the end.

At each position i, we will iterate through the possible next positions j that can be reached from i. We will update the dp[j] if it can be reached with a smaller cost and update the path[j] accordingly.

Finally, we will reconstruct the path from the start to the end using the path array.

Time Complexity

The time complexity of this solution is O(n^2) where n is the length of the input array.

Space Complexity

The space complexity of this solution is O(n) where n is the length of the input array.

Solution Code

class Solution {
    public List<Integer> cheapestJump(int[] coins, int maxJump) {
        int n = coins.length;
        int[] dp = new int[n];
        int[] path = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[n - 1] = coins[n - 1];

        for (int i = n - 2; i >= 0; i--) {
            if (coins[i] == -1) continue;

            for (int j = i + 1; j <= Math.min(i + maxJump, n - 1); j++) {
                if (dp[j] == Integer.MAX_VALUE) continue;

                int cost = coins[i] + dp[j];
                if (cost < dp[i] || (cost == dp[i] && path[j] < path[i])) {
                    dp[i] = cost;
                    path[i] = j + 1;
                }
            }
        }

        List<Integer> result = new ArrayList<>();
        if (dp[0] == Integer.MAX_VALUE) return result;

        int pos = 0;
        while (pos < n - 1) {
            result.add(pos + 1);
            pos = path[pos] - 1;
        }
        result.add(n);

        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 656 (Coin Path)?

This page provides optimized solutions for LeetCode problem 656 (Coin Path) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 656 (Coin Path)?

The time complexity for LeetCode 656 (Coin Path) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 656 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 656 in Java, C++, or Python.

Back to LeetCode Solutions