Jump game ix

Array Dynamic Programming

23.9% acceptance

Feb 25, 2026

180

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_value(nums: Vec<i32>) -> Vec<i32> {
    let n = nums.len();
    // Edge (i,j) exists iff i < j and nums[i] > nums[j].
    // The same condition applies to both forward and backward jumps,
    // so the graph is undirected. The answer for each node is the max
    // value in its connected component.
    //
    // Use Union-Find + monotone stack (non-decreasing, bottom→top):
    // Process left to right. For node j, union with all earlier
    // components whose max value > nums[j] (they share an inversion edge).
    let mut parent: Vec<usize> = (0..n).collect();
    let mut comp_max: Vec<i32> = nums.clone();

    // Stack stores (component_max, root_index) in non-decreasing order.
    let mut stack: Vec<(i32, usize)> = Vec::new();

    for j in 0..n {
      let v = nums[j];
      let cur_root = j;

      while let Some(&(top_max, top_root)) = stack.last() {
        if top_max > v {
          stack.pop();
          // Union top_root into cur_root.
          parent[top_root] = cur_root;
          comp_max[cur_root] = comp_max[cur_root].max(comp_max[top_root]);
        } else {
          break;
        }
      }
      stack.push((comp_max[cur_root], cur_root));
    }

    // Build result: for each i, find its root and return comp_max[root].
    let mut result = vec![0i32; n];
    for i in 0..n {
      // Find root with path compression.
      let mut r = i;
      while parent[r] != r {
        r = parent[r];
      }
      let mut x = i;
      while parent[x] != r {
        let next = parent[x];
        parent[x] = r;
        x = next;
      }
      result[i] = comp_max[r];
    }
    result
  }
}