Watch 3 video solutions for Jump Game VIII, a medium level problem involving Array, Dynamic Programming, Stack. This walkthrough by Code-Yao has 1,378 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array nums of length n. You are initially standing at index 0. You can jump from index i to index j where i < j if:
nums[i] <= nums[j] and nums[k] < nums[i] for all indexes k in the range i < k < j, ornums[i] > nums[j] and nums[k] >= nums[i] for all indexes k in the range i < k < j.You are also given an integer array costs of length n where costs[i] denotes the cost of jumping to index i.
Return the minimum cost to jump to the index n - 1.
Example 1:
Input: nums = [3,2,4,4,1], costs = [3,7,6,4,2] Output: 8 Explanation: You start at index 0. - Jump to index 2 with a cost of costs[2] = 6. - Jump to index 4 with a cost of costs[4] = 2. The total cost is 8. It can be proven that 8 is the minimum cost needed. Two other possible paths are from index 0 -> 1 -> 4 and index 0 -> 2 -> 3 -> 4. These have a total cost of 9 and 12, respectively.
Example 2:
Input: nums = [0,1,2], costs = [1,1,1] Output: 2 Explanation: Start at index 0. - Jump to index 1 with a cost of costs[1] = 1. - Jump to index 2 with a cost of costs[2] = 1. The total cost is 2. Note that you cannot jump directly from index 0 to index 2 because nums[0] <= nums[1].
Constraints:
n == nums.length == costs.length1 <= n <= 1050 <= nums[i], costs[i] <= 105Problem Overview: You are given an array nums and a cost array. Starting at index 0, you can jump to certain indices based on value constraints in nums. Each landing adds a cost, and the goal is to reach the last index with the minimum total cost.
Approach 1: Graph + Dynamic Programming (Naive Transitions) (O(n²) time, O(n) space)
Model the array as a directed graph where each index is a node. From index i, check every valid j > i that satisfies the problem’s monotonic conditions on nums. Run a dynamic programming or shortest-path style transition: dp[j] = min(dp[j], dp[i] + cost[j]). This approach directly simulates all possible edges by iterating forward and verifying the value constraints.
The downside is the quadratic scan when checking all possible next indices. For large arrays this quickly becomes too slow, but it clarifies the underlying structure: the problem is essentially a shortest-path problem over an implicit graph. Understanding this version helps before optimizing with stacks.
Approach 2: Monotonic Stack + Dynamic Programming (O(n) time, O(n) space)
The optimal solution observes that valid jumps correspond to the next greater or next smaller structure in the nums array. Instead of scanning forward for every index, maintain two monotonic stacks: one increasing and one decreasing. As you iterate through indices, you pop elements that violate the monotonic condition and immediately update the DP transition for those indices.
Let dp[i] represent the minimum cost to reach index i. While processing index i, pop indices from the decreasing stack while nums[stack.top] > nums[i] and update dp[i] = min(dp[i], dp[top] + cost[i]). Do the symmetric operation with the increasing stack for the opposite constraint. Each index is pushed and popped at most once, giving linear complexity.
This technique combines dynamic programming with a monotonic stack to efficiently discover valid transitions that would otherwise require scanning. Conceptually, you are computing shortest paths in an implicit graph, but pruning edges using stack ordering. The result is an O(n) algorithm that scales well even for large inputs.
Recommended for interviews: Start by explaining the DP interpretation as a shortest-path problem on indices. Then show why naive transitions become O(n²). Interviewers typically expect the monotonic stack optimization because it demonstrates pattern recognition with next-greater/next-smaller structures and efficient DP state transitions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph Modeling + DP (Naive Transitions) | O(n²) | O(n) | Useful for understanding the problem as a shortest-path over indices or when constraints are very small. |
| Monotonic Stack + Dynamic Programming | O(n) | O(n) | Best approach for interviews and production constraints. Efficiently finds valid transitions using stack ordering. |