Jump Game IX

Problem

We are given an array nums.

From index i, we can jump:

• to the right, j > i, only when nums[j] < nums[i]
• to the left, j < i, only when nums[j] > nums[i]

For every starting index, we need the maximum value that can be reached after any number of valid jumps.

Key Idea

Think of two indices as connected when they form an inversion:

i < j and nums[i] > nums[j]

Why?

Because i can jump right to j, and j can jump left to i. So once two positions form this pair, they belong to the same reachable group.

Inside one reachable group, every index has the same answer: the maximum value in that group.

So the problem becomes:

Split the array into connected components, then fill every component with its maximum value.

Why Components Are Continuous

Process the array from left to right.

Suppose we already have connected components on the left. Each component is a continuous segment, and its stored value is the maximum value inside that segment.

Now we read nums[i].

If the last component has maximum value greater than nums[i], then there is some index in that component with value > nums[i]. Since that index is on the left and i is on the right, nums[i] can jump left to it, and that value can jump right to i.

So the current element and that component must merge.

If the previous component also has a maximum greater than nums[i], it also merges, and so on.

This is exactly a monotonic stack pattern.

Monotonic Stack

Each stack item stores:

(component maximum, left boundary, right boundary)

The stack keeps component maximums in non-decreasing order.

For each nums[i]:

1. Start a new component [i, i].
2. While the previous component maximum is greater than nums[i], merge it into the current component.
3. Push the merged component back.
4. After the scan, every component writes its maximum value into the answer array.

The comparison uses the original nums[i], not the merged maximum. That is important because nums[i] is the new right-side value that creates inversion pairs with components on the left.

import java.util.ArrayList;
import java.util.List;

class Solution {
    record Component(int value, int left, int right) {}

    public int[] maxValue(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        List<Component> stack = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            Component curr = new Component(nums[i], i, i);

            while (!stack.isEmpty() && stack.get(stack.size() - 1).value() > nums[i]) {
                Component top = stack.remove(stack.size() - 1);
                curr = new Component(
                    Math.max(curr.value(), top.value()),
                    top.left(),
                    curr.right()
                );
            }

            stack.add(curr);
        }

        for (Component component : stack) {
            for (int i = component.left(); i <= component.right(); i++) {
                ans[i] = component.value();
            }
        }

        return ans;
    }
}

Dry Run

Take:

nums = [2, 3, 1]

Start with an empty stack.

Index 0

nums[0] = 2

Push component:

[(max=2, range=0..0)]

Index 1

nums[1] = 3

The previous component maximum 2 is not greater than 3, so no merge happens.

[(max=2, range=0..0), (max=3, range=1..1)]

Index 2

nums[2] = 1

The previous maximum 3 > 1, so merge index 1. Now the current component is:

(max=3, range=1..2)

The previous maximum 2 > 1, so merge index 0 too. Now:

(max=3, range=0..2)

Final stack:

[(max=3, range=0..2)]

So every index can reach 3, and the answer is:

[3, 3, 3]

Why This Works

If nums[i] is smaller than a component maximum on its left, it forms an inversion with some value inside that component. That makes nums[i] reachable from the component and the component reachable from nums[i].

Once a merge happens, the new component maximum becomes the maximum of all merged parts. Since components on the stack have non-decreasing maximums, every component that can be connected to nums[i] is popped in one continuous block from the end of the stack.

Components that remain on the stack have maximum value <= nums[i], so nums[i] cannot form a valid left jump into them. They stay separate.

Complexity

Let n be the length of nums.

• Time complexity: O(n)
• Space complexity: O(n)

Each component is pushed once and popped at most once, so the stack work is linear. The final fill over all component ranges also touches each index once.

Final Takeaway

The jump rules look directional, but every inversion pair creates two-way reachability.

That turns the problem into connected components over continuous array segments. Maintaining those segments with a monotonic stack gives a clean O(n) solution.