LeetCode 3660 - Jump Game IX

The problem asks us to determine, for each position in an array nums, the maximum value that can be reached by making a series of jumps under strict rules.

leetcodemediumarraydynamic-programming

LeetCode Problem 3660

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem asks us to determine, for each position in an array nums, the maximum value that can be reached by making a series of jumps under strict rules. From any index i, we can jump forward to an index j > i only if nums[j] < nums[i], or jump backward to an index j < i only if nums[j] > nums[i]. Essentially, forward jumps must go to smaller numbers, and backward jumps must go to larger numbers.

The input is an array of integers nums of length up to 105, with each element up to 109. This means brute-force exploration of all possible jump sequences is likely too slow, so an efficient approach is needed. The output is an array ans where ans[i] is the maximum value reachable starting from index i.

Important edge cases include arrays of length 1, arrays where all elements are the same, strictly increasing or decreasing arrays, and arrays with local minima or maxima where jumps might chain in non-obvious ways.

Approaches

A brute-force approach would explore all valid jump sequences starting from each index. For index i, we would recursively check all reachable indices and track the maximum value seen. This approach is correct but extremely inefficient because the number of sequences can grow exponentially with array length, making it infeasible for arrays of size up to 105.

The key insight for an optimal solution is to leverage dynamic programming combined with a monotonic stack. If we process indices in an order based on the values of nums, we can use previously computed maximums to determine the maximum for the current index efficiently. Specifically, we can compute the maximum reachable value for indices in increasing order to handle backward jumps and in decreasing order to handle forward jumps. A monotonic stack allows us to efficiently find jump targets that satisfy the forward or backward constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Recursively explores all jump sequences, infeasible for large arrays
Optimal O(n log n) O(n) Uses dynamic programming with monotonic stacks to compute maximum reachable values efficiently

Algorithm Walkthrough

  1. Create an array ans of length n initialized with the values of nums. This ensures each index at least reaches itself.
  2. Sort indices of nums in increasing order of nums[i]. This allows us to handle backward jumps efficiently since backward jumps can only go to larger values.
  3. Use a monotonic stack while iterating the sorted indices. For each index i, update ans[i] to the maximum of its current value and ans[j] for indices j that can jump to i.
  4. Sort indices of nums in decreasing order of nums[i] to handle forward jumps efficiently since forward jumps can only go to smaller values.
  5. Repeat the monotonic stack process for forward jumps.
  6. Return the ans array as the result.

Why it works: By processing indices in increasing and decreasing value order, we ensure that for each index, all potential jump targets (either backward or forward) have their maximum reachable values already computed. The monotonic stack allows us to efficiently find these targets without checking every index.

Python Solution

from typing import List

class Solution:
    def maxValue(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = nums.copy()
        
        # Handle backward jumps (j < i, nums[j] > nums[i])
        sorted_inc = sorted(range(n), key=lambda i: nums[i])
        stack = []
        for i in sorted_inc:
            while stack and stack[-1] < i:
                j = stack.pop()
                if nums[j] > nums[i]:
                    ans[i] = max(ans[i], ans[j])
            stack.append(i)
        
        # Handle forward jumps (j > i, nums[j] < nums[i])
        sorted_dec = sorted(range(n), key=lambda i: -nums[i])
        stack = []
        for i in sorted_dec:
            while stack and stack[-1] > i:
                j = stack.pop()
                if nums[j] < nums[i]:
                    ans[i] = max(ans[i], ans[j])
            stack.append(i)
        
        return ans

This implementation first handles backward jumps by iterating indices in increasing value order and using a stack to track potential larger jump targets. Then, it handles forward jumps by iterating in decreasing value order. At each step, the ans array is updated with the maximum reachable value, ensuring correctness without redundant computation.

Go Solution

package main

func maxValue(nums []int) []int {
    n := len(nums)
    ans := make([]int, n)
    copy(ans, nums)

    type pair struct {
        val int
        idx int
    }

    // Backward jumps (j < i, nums[j] > nums[i])
    inc := make([]pair, n)
    for i, v := range nums {
        inc[i] = pair{v, i}
    }
    sort.Slice(inc, func(i, j int) bool { return inc[i].val < inc[j].val })

    stack := []int{}
    for _, p := range inc {
        i := p.idx
        for len(stack) > 0 && stack[len(stack)-1] < i {
            j := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if nums[j] > nums[i] {
                if ans[j] > ans[i] {
                    ans[i] = ans[j]
                }
            }
        }
        stack = append(stack, i)
    }

    // Forward jumps (j > i, nums[j] < nums[i])
    dec := make([]pair, n)
    for i, v := range nums {
        dec[i] = pair{v, i}
    }
    sort.Slice(dec, func(i, j int) bool { return dec[i].val > dec[j].val })

    stack = []int{}
    for _, p := range dec {
        i := p.idx
        for len(stack) > 0 && stack[len(stack)-1] > i {
            j := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if nums[j] < nums[i] {
                if ans[j] > ans[i] {
                    ans[i] = ans[j]
                }
            }
        }
        stack = append(stack, i)
    }

    return ans
}

In Go, slices and structs are used to store index-value pairs. Sorting and stack operations are implemented using built-in slices. Copying arrays ensures ans starts with the original values of nums.

Worked Examples

Example 1: nums = [2,1,3]

After backward processing:

i nums[i] Stack ans
1 1 [1] 1
0 2 [0] 2
2 3 [2] 3

After forward processing:

i nums[i] Stack ans
2 3 [2] 3
0 2 [0] 2
1 1 [1] 2

Final result: [2, 2, 3]

Example 2: nums = [2,3,1]

After backward processing:

i nums[i] Stack ans
2 1 [2] 1
0 2 [0] 2
1 3 [1] 3

After forward processing:

i nums[i] Stack ans
1 3 [1] 3
0 2 [0] 3
2 1 [2] 3

Final result: [3, 3, 3]

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting indices takes O(n log n) and stack operations are O(n) overall
Space O(n) Stack and ans array both require O(n) space

Sorting is the dominant factor. Using monotonic stacks ensures each index is processed a constant number of times.

Test Cases

# Provided examples
assert Solution().maxValue([2,1,3]) == [2,2,3]  # basic forward/backward jumps
assert Solution().maxValue([2,3,1]) == [3,3,3]  # forward jump chaining

# Edge cases
assert Solution().maxValue([1]) == [1]  # single element
assert Solution().maxValue([1,1,1]) == [1,1,1]  # all equal elements
assert Solution().maxValue([1,2,3,4,5]) == [5,5,5,5,5]  # strictly increasing
assert Solution().maxValue([5,4,3,2,1]) == [5,4,3,2,1]  # strictly decreasing
assert Solution().maxValue([3,1,4,2,5]) == [5,4