Coin Path - Solution & Explanation

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.