You are given an integer array nums.
From any index i, you can jump to another index j under the following rules:
j where j > i is allowed only if nums[j] < nums[i].j where j < i is allowed only if nums[j] > nums[i].For each index i, find the maximum value in nums that can be reached by following any sequence of valid jumps starting at i.
Return an array ans where ans[i] is the maximum value reachable starting from index i.
Example 1:
Input: nums = [2,1,3]
Output: [2,2,3]
Explanation:
i = 0: No jump increases the value.i = 1: Jump to j = 0 as nums[j] = 2 is greater than nums[i].i = 2: Since nums[2] = 3 is the maximum value in nums, no jump increases the value.Thus, ans = [2, 2, 3].
Example 2:
Input: nums = [2,3,1]
Output: [3,3,3]
Explanation:
i = 0: Jump forward to j = 2 as nums[j] = 1 is less than nums[i] = 2, then from i = 2 jump to j = 1 as nums[j] = 3 is greater than nums[2].i = 1: Since nums[1] = 3 is the maximum value in nums, no jump increases the value.i = 2: Jump to j = 1 as nums[j] = 3 is greater than nums[2] = 1.Thus, ans = [3, 3, 3].
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109Problem Overview: You are given an array where each position represents a state you can jump from. The goal is to determine the minimum number of jumps required to reach the final index while following the allowed transition rules between indices.
Approach 1: Recursive DP with Memoization (O(n2) time, O(n) space)
Start with a top-down dynamic programming strategy. From index i, recursively try all valid next indices j that satisfy the jump rule defined in the problem. Each recursive call returns the minimum jumps needed from that position to the end. Store computed results in a memo array so repeated states are not recomputed. The key idea is treating each index as a subproblem: dp[i] stores the minimum jumps required from i. In the worst case you examine up to n transitions for every index, giving O(n²) time and O(n) space for memo storage.
Approach 2: Bottom-Up Dynamic Programming (O(n2) time, O(n) space)
Instead of recursion, compute results iteratively. Define dp[i] as the minimum jumps required to reach index i. Initialize dp[0] = 0, then iterate through the array and attempt transitions to later indices that satisfy the allowed jump conditions. Whenever a valid jump from i to j exists, update dp[j] = min(dp[j], dp[i] + 1). This avoids recursion overhead and gives a straightforward dynamic programming table. The nested iteration over possible transitions still results in O(n²) time complexity and O(n) auxiliary space.
Approach 3: Optimized Dynamic Programming with Monotonic Structure (O(n) time, O(n) space)
The quadratic bottleneck comes from repeatedly scanning candidate jumps. You can optimize this using a monotonic stack or ordered structure to maintain indices that satisfy the jump constraints as you sweep through the array. Instead of checking every previous position, you maintain candidate indices whose values maintain a monotonic property. Each index enters and leaves the structure once, allowing constant-time transitions to the next valid state. The dynamic programming relation still tracks dp[i], but candidate transitions are discovered in amortized constant time. This reduces the total runtime to O(n) with O(n) extra space for the stack and DP array.
Recommended for interviews: Start by describing the straightforward dynamic programming formulation using dp[i] to represent the minimum jumps from or to an index. That shows you understand the state transition. Then explain how repeated scanning causes O(n²) time and introduce the optimized solution using a monotonic structure over the array. Interviewers usually expect the optimized DP because it demonstrates control over both DP state design and data-structure-driven optimization.
If i = n - 1, then it can jump to the maximum value in nums, so ans[i] = max(nums). For other positions i, we can calculate by maintaining a prefix maximum array and a suffix minimum variable.
The specific steps are as follows:
preMax, where preMax[i] represents the maximum value in the interval [0, i] when traversing from left to right.sufMin, which represents the minimum value to the right of the current element when traversing from right to left. Initially sufMin = infty.preMax array.i, if preMax[i] > sufMin, it means we can jump from i to the position where preMax is located, then jump to the position where sufMin is located, and finally jump to i + 1. Therefore, the numbers that can be reached from i + 1 can also be reached from i, so ans[i] = ans[i + 1]; otherwise update to preMax[i]. Then update sufMin.ans.Time complexity O(n), space complexity O(n). Where n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DP with Memoization | O(n^2) | O(n) | Good for explaining the core state transition and building intuition |
| Bottom-Up Dynamic Programming | O(n^2) | O(n) | Preferred when avoiding recursion and implementing a clear DP table |
| Optimized DP with Monotonic Stack | O(n) | O(n) | Best for large inputs where quadratic scanning is too slow |
Jump Game IX | Q3. Weekly Contest 464 • ExpertFunda • 1,443 views views
Watch 6 more video solutions →Practice Jump Game IX with our built-in code editor and test cases.
Practice on FleetCode