Skip to main content
Talentd

Coin Path - Solution & Explanation

HardPremiumFree on FleetCodeArrayDynamic Programming6 min readAsked at: Google
Practice this problem

Problem Statement

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 = [Pa1, Pa2, ..., Pax] of length x is lexicographically smaller than p2 = [Pb1, Pb2, ..., Pbx] of length y, if and only if at the first j where Paj and Pbj differ, Paj < Pbj; 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

Approach Overview

Problem Overview: You are given an array coins where coins[i] is the cost to land on index i. Some positions contain -1, meaning they are blocked. Starting at index 0, you can jump at most B steps forward. The goal is to reach the last index with the minimum total cost and return the path of indices taken. If multiple paths have the same cost, return the lexicographically smallest path.

Approach 1: Brute Force DFS (Exponential Time, Exponential Space)

Start from index 0 and recursively try every jump from 1 to B. Skip blocked cells (-1). Track the cumulative cost and keep the path with the smallest total cost. This explores every possible path to the end, which leads to O(B^n) time in the worst case and large recursion overhead. The approach demonstrates the search space clearly but becomes impractical for larger arrays.

Approach 2: Dynamic Programming from Right to Left (O(nB) time, O(n) space)

This is the standard solution using dynamic programming. Define dp[i] as the minimum cost needed to reach the end starting from index i. Traverse the array from right to left. For each index, check every reachable position j where i < j ≤ i + B. If coins[i] is not blocked and dp[j] is valid, update dp[i] = coins[i] + dp[j]. Store the chosen next index to reconstruct the path later.

Lexicographically smallest path naturally emerges because indices are evaluated in increasing order. After filling the DP table, reconstruct the path by following the stored next pointers starting from index 0. This approach processes each index and up to B jumps, giving O(nB) time and O(n) space.

Approach 3: Sliding Window Optimization with Deque (O(n) time, O(n) space)

The DP transition requires finding the minimum dp[j] within the window [i+1, i+B]. Instead of scanning all B positions, maintain a monotonic deque storing candidate indices with increasing dp values. As you move left across the array, remove indices that fall outside the window and keep the deque ordered by minimal cost. The front always gives the optimal next step.

This converts the transition to constant-time amortized operations and reduces the total complexity to O(n). The technique combines array traversal with a monotonic deque structure. Path reconstruction still uses a next pointer array.

Recommended for interviews: The dynamic programming from right to left solution with O(nB) time is what most interviewers expect. It clearly shows state definition, transition logic, and path reconstruction. Mentioning the deque optimization demonstrates deeper algorithmic awareness and earns extra points when discussing performance improvements.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force DFSO(B^n)O(n)Conceptual baseline to understand the search space and constraints
Dynamic Programming (Right to Left)O(nB)O(n)General solution expected in interviews; straightforward DP with path reconstruction
DP with Monotonic Deque OptimizationO(n)O(n)Large inputs where jump window B is large and O(nB) becomes expensive

Video Solution

656. Coin Path - Week 3/5 Leetcode October Challenge • Programming Live with Larry • 463 views views

Watch 1 more video solutions →

Frequently Asked Questions

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).

Ready to solve this problem?

Practice Coin Path with our built-in code editor and test cases.

Practice on FleetCode
Previous

House Robber

Next

House Robber II