3660. Jump Game IX - Solution & Explanation

The problem

You are given an integer array nums.

From any index i, you can jump to another index j under the following rules:

Jump to index j where j > i is allowed only if nums[j] < nums[i].
Jump to index 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:

For i = 0: No jump increases the value.
For i = 1: Jump to j = 0 as nums[j] = 2 is greater than nums[i].
For 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:

For 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].
For i = 1: Since nums[1] = 3 is the maximum value in nums, no jump increases the value.
For 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 <= 10⁵
1 <= nums[i] <= 10⁹

Approach overview

Problem 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(n²) 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(n²) 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.

Solution

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:

Create an array preMax, where preMax[i] represents the maximum value in the interval [0, i] when traversing from left to right.
Create a variable sufMin, which represents the minimum value to the right of the current element when traversing from right to left. Initially sufMin = infty.
First preprocess the preMax array.
Next, traverse the array from right to left. For each position 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.
Finally return the result array ans.

Time complexity O(n), space complexity O(n). Where n is the length of the array nums.

Python

class Solution:
    def maxValue(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        pre_max = [nums[0]] * n
        for i in range(1, n):
            pre_max[i] = max(pre_max[i - 1], nums[i])
        suf_min = inf
        for i in range(n - 1, -1, -1):
            ans[i] = ans[i + 1] if pre_max[i] > suf_min else pre_max[i]
            suf_min = min(suf_min, nums[i])
        return ans

Java

class Solution {
    public int[] maxValue(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        int[] preMax = new int[n];
        preMax[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            preMax[i] = Math.max(preMax[i - 1], nums[i]);
        }
        int sufMin = 1 << 30;
        for (int i = n - 1; i >= 0; --i) {
            ans[i] = preMax[i] > sufMin ? ans[i + 1] : preMax[i];
            sufMin = Math.min(sufMin, nums[i]);
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<int> maxValue(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        vector<int> preMax(n, nums[0]);
        for (int i = 1; i < n; ++i) {
            preMax[i] = max(preMax[i - 1], nums[i]);
        }
        int sufMin = 1 << 30;
        for (int i = n - 1; i >= 0; --i) {
            ans[i] = preMax[i] > sufMin ? ans[i + 1] : preMax[i];
            sufMin = min(sufMin, nums[i]);
        }
        return ans;
    }
};

TypeScript

function maxValue(nums: number[]): number[] {
    const n = nums.length;
    const ans = Array(n).fill(0);
    const preMax = Array(n).fill(nums[0]);
    for (let i = 1; i < n; i++) {
        preMax[i] = Math.max(preMax[i - 1], nums[i]);
    }
    let sufMin = 1 << 30;
    for (let i = n - 1; i >= 0; i--) {
        ans[i] = preMax[i] > sufMin ? ans[i + 1] : preMax[i];
        sufMin = Math.min(sufMin, nums[i]);
    }
    return ans;
}

func maxValue(nums []int) []int {
	n := len(nums)
	ans := make([]int, n)
	preMax := make([]int, n)
	preMax[0] = nums[0]
	for i := 1; i < n; i++ {
		preMax[i] = max(preMax[i-1], nums[i])
	}
	sufMin := 1 << 30
	for i := n - 1; i >= 0; i-- {
		if preMax[i] > sufMin {
			ans[i] = ans[i+1]
		} else {
			ans[i] = preMax[i]
		}
		sufMin = min(sufMin, nums[i])
	}
	return ans
}

Try this approach in the editor

Complexity analysis

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

Frequently asked questions

Is Jump Game IX easy or hard?

Jump Game IX is typically classified as Medium difficulty. The base dynamic programming idea is straightforward, but achieving optimal performance requires recognizing the repeated transition pattern and applying a monotonic data structure optimization.

Jump Game IX Python/Java solution

The solution can be implemented using dynamic programming in Python, Java, C++, Go, or TypeScript. Maintain a dp array where dp[i] stores the minimum jumps to reach or leave index i, and update it using valid transitions discovered during iteration.

How to solve Jump Game IX in O(n)?

Track the minimum jumps using a DP array while maintaining a monotonic structure of candidate indices that satisfy the jump constraints. As you iterate through the array, update dp values using the best candidate and remove invalid states from the structure. Each index enters and exits the structure once, giving O(n) time.

What is the best approach for Jump Game IX?

The most efficient approach uses dynamic programming combined with a monotonic stack or ordered structure to avoid scanning all previous indices. This optimization reduces the complexity from O(n^2) to O(n). Each index is processed once while maintaining candidate jump positions.

Is Jump Game IX asked at Google/Amazon/Meta?

Jump Game style problems are common in interviews at companies like Google, Amazon, and Meta because they test dynamic programming state design and optimization techniques. Variants frequently appear in coding rounds focusing on arrays and DP transitions.

What data structure is used in Jump Game IX?

The core solution uses a dynamic programming array to track the minimum jumps for each index. The optimized version often adds a monotonic stack or similar structure to efficiently maintain candidate transitions and eliminate the quadratic scan.

What is the time complexity of Jump Game IX?

A straightforward dynamic programming solution takes O(n^2) time because each index may evaluate transitions to many other indices. With a monotonic stack optimization, the complexity improves to O(n) while still using O(n) space for the DP array.

Jump Game IX solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Jump Game IX solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems