Is Coin Path easy or hard?

Coin Path is classified as a Hard problem because it combines dynamic programming, window optimization, and lexicographically smallest path reconstruction. The DP transition itself is manageable, but correctly handling blocked cells and path ordering adds complexity.

Coin Path Python/Java solution

Most implementations compute a DP array from the end of the array toward the start and store the next index for reconstruction. The same logic translates directly across Python, Java, C++, Go, and TypeScript since it only requires arrays and simple loops.

How to solve Coin Path in O(n)?

Maintain a monotonic deque that stores candidate indices with the smallest dp values within the sliding window [i+1, i+B]. While iterating from right to left, remove indices outside the window and keep the deque sorted by dp cost. This allows retrieving the best next step in constant time, reducing the DP transition to O(n) overall.

What is the best approach for Coin Path?

Dynamic programming from right to left is the most common approach. Define dp[i] as the minimum cost to reach the end from index i and check all jumps within B positions. This solution runs in O(nB) time and O(n) space and also allows easy reconstruction of the lexicographically smallest path.

Is Coin Path asked at Google/Amazon/Meta?

Coin Path is a dynamic programming path reconstruction problem similar to questions used by companies like Google, Amazon, and Meta. Variations of minimum-cost path with constraints appear frequently in interviews to test DP state design and optimization skills.

What data structure is used in Coin Path?

The core solution uses arrays for dynamic programming and path reconstruction. An optimized version also uses a deque to maintain the minimum DP value inside a sliding window, reducing the transition cost from O(B) to amortized O(1).

What is the time complexity of Coin Path?

The typical dynamic programming solution runs in O(nB) time because each index evaluates up to B forward jumps. Space complexity is O(n) for the DP array and path tracking. With a monotonic deque optimization, the time complexity can be improved to O(n).

Description Solution Video 13:36

656. Coin Path

Hard34.2% acceptance1 companyPremium elsewhere, free here

You are given an integer array coins (1-indexed) of length n and an integer maxJump. You can jump to any index i of the array coins if coins[i] != -1 and you have to pay coins[i] when you visit index i. In addition to that, if you are currently at index i, you can only jump to any index i + k where i + k <= n and k is a value in the range [1, maxJump].

You are initially positioned at index 1 (coins[1] is not -1). You want to find the path that reaches index n with the minimum cost.

Return an integer array of the indices that you will visit in order so that you can reach index n with the minimum cost. If there are multiple paths with the same cost, return the lexicographically smallest such path. If it is not possible to reach index n, return an empty array.

A path p1 = [Pa₁, Pa₂, ..., Pa_x] of length x is lexicographically smaller than p2 = [Pb₁, Pb₂, ..., Pb_x] of length y, if and only if at the first j where Pa_j and Pb_j differ, Pa_j < Pb_j; when no such j exists, then x < y.

Example 1:

Input: coins = [1,2,4,-1,2], maxJump = 2
Output: [1,3,5]

Example 2:

Input: coins = [1,2,4,-1,2], maxJump = 1
Output: []

Constraints:

1 <= coins.length <= 1000
-1 <= coins[i] <= 100
coins[1] != -1
1 <= maxJump <= 100

Asked at 1 company

Google

Topics

Array Dynamic Programming

13:36

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

656. Coin Path

Asked at 1 company

Topics

Similar problems