3660. Jump Game IX

Array
Graph
Prefix Maximum
Suffix Minimum

TIME

O(n)

SPACE

O(n)

Intuition

For any pair i < j, jumps are possible in both directions exactly when nums[i] > nums[j]:

from i to j, because j > i and nums[j] < nums[i]
from j to i, because i < j and nums[i] > nums[j]

So indices connected through valid jumps are the connected components of the inversion graph.

A boundary between i and i + 1 separates two components only if there is no inversion crossing it. That means every value on the left must be less than or equal to every value on the right:

max(nums[0..i]) <= min(nums[i + 1..n - 1])

If this condition is false, at least one inversion crosses the boundary, so both sides belong to the same reachable component.

Approach

Build suffix_min, where suffix_min[i] is the minimum value from i to the end.
Scan from left to right while tracking:
- start, the start index of the current component
- component_max, the maximum value in the current component
At index i, the current component ends if:
- i is the last index, or
- component_max <= suffix_min[i + 1]
When a component ends, fill every answer in that component with component_max.

Complexity

Time: O(n), one suffix pass and one scan
Space: O(n), for suffix_min and the answer array

Edge Cases

Strictly increasing array → no inversions, every index is its own component
Strictly decreasing array → all indices are connected
Duplicate values → equal values do not create jumps, so the split condition uses <=

Code

from typing import List


class Solution:
    def maxValue(self, nums: List[int]) -> List[int]:
        """
        3660. Jump Game IX
        Time: O(n)
        Space: O(n)
        """
        n = len(nums)
        suffix_min = nums[:]

        for i in range(n - 2, -1, -1):
            suffix_min[i] = min(nums[i], suffix_min[i + 1])

        ans = [0] * n
        start = 0
        component_max = nums[0]

        for i, num in enumerate(nums):
            component_max = max(component_max, num)

            if i == n - 1 or component_max <= suffix_min[i + 1]:
                for j in range(start, i + 1):
                    ans[j] = component_max

                if i + 1 < n:
                    start = i + 1
                    component_max = nums[start]

        return ans

/**
 * 3660. Jump Game IX
 * Time: O(n)
 * Space: O(n)
 */
class Solution {
    public int[] maxValue(int[] nums) {
        int n = nums.length;
        int[] suffixMin = new int[n];
        suffixMin[n - 1] = nums[n - 1];

        for (int i = n - 2; i >= 0; i--) {
            suffixMin[i] = Math.min(nums[i], suffixMin[i + 1]);
        }

        int[] ans = new int[n];
        int start = 0;
        int componentMax = nums[0];

        for (int i = 0; i < n; i++) {
            componentMax = Math.max(componentMax, nums[i]);

            if (i == n - 1 || componentMax <= suffixMin[i + 1]) {
                for (int j = start; j <= i; j++) {
                    ans[j] = componentMax;
                }

                if (i + 1 < n) {
                    start = i + 1;
                    componentMax = nums[start];
                }
            }
        }

        return ans;
    }
}