Jump Game VIII - Solution & Explanation
Problem Statement
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]andnums[k] < nums[i]for all indexeskin the rangei < k < j, ornums[i] > nums[j]andnums[k] >= nums[i]for all indexeskin the rangei < 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] <= 105
Approach Overview
Problem 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.
Solution
According to the problem description, we need to find the next position j where nums[j] is greater than or equal to nums[i], and the next position j where nums[j] is less than nums[i]. We can use a monotonic stack to find these two positions in O(n) time, and then construct an adjacency list g, where g[i] represents the indices that index i can jump to.
Then we use dynamic programming to find the minimum cost. Let f[i] represent the minimum cost to jump to index i. Initially, f[0] = 0 and the rest f[i] = infty. We enumerate the indices i from small to large. For each i, we enumerate each index j in g[i] and perform the state transition f[j] = min(f[j], f[i] + costs[j]). The answer is f[n - 1].
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array.
Code
Python
Java
C++
Go
TypeScript
Detailed Complexity Analysis
| 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. |
Video Solution
Leetcode 2297. Jump Game VIII - Dynamic Programming and monotonic stacks • Code-Yao • 1,396 views views
Watch 2 more video solutions →Frequently Asked Questions
Is Jump Game VIII easy or hard?
How to solve Jump Game VIII in O(n)?
Jump Game VIII Python or Java solution?
What is the best approach for Jump Game VIII?
Is Jump Game VIII asked at Google/Amazon/Meta?
What data structure is used in Jump Game VIII?
What is the time complexity of Jump Game VIII?
Ready to solve this problem?
Practice Jump Game VIII with our built-in code editor and test cases.
Practice on FleetCode