Problem Description

You are given an integer array nums. From any index i, you can jump to other indices following specific rules:

• You can jump forward from index i to index j (where j > i) only if nums[j] < nums[i]
• You can jump backward from index i to index j (where j < i) only if nums[j] > nums[i]

In other words, when jumping forward, you must land on a smaller value, and when jumping backward, you must land on a larger value.

For each starting index i, you need to find the maximum value in nums that can be reached by following any valid sequence of jumps. You can make multiple jumps in sequence as long as each individual jump follows the rules above.

Return an array ans where ans[i] represents the maximum value that can be reached starting from index i.

For example, if you start at index i, you might jump forward to a smaller value at index j, then from j jump backward to a larger value at index k, and continue jumping following the rules. Among all values you can reach through any valid jumping sequence, ans[i] should be the maximum one.

Intuition

Let's think about the jumping pattern. From any index i, we can jump forward to smaller values and backward to larger values. This creates an alternating pattern: if we jump forward (to a smaller value), the next jump from there must be backward (to a larger value), and vice versa.

A key observation is that if we're at position i and want to maximize the value we can reach, we should consider what happens when we make our first jump. If we jump forward to some position j where nums[j] < nums[i], then from j we can only jump backward to positions with larger values than nums[j].

Here's the critical insight: if there exists a position to the left of i with the maximum possible value (let's call it preMax[i]), and a position to the right of i with the minimum possible value (let's call it sufMin), we can potentially create a jumping sequence that reaches both extremes.

Consider this scenario: if preMax[i] > sufMin, it means the maximum value to the left is greater than some minimum value to the right. We can jump from i to the position of sufMin (forward jump to smaller value), then from there jump back to the position of preMax[i] (backward jump to larger value). This allows us to reach the maximum value in the left portion.

However, if preMax[i] ≤ sufMin, we cannot make this beneficial jumping pattern, so the best we can reach is just preMax[i] itself.

The clever part is processing from right to left. When we're at position i, we already know ans[i+1] (the maximum reachable from i+1). If we can establish the jumping pattern described above (preMax[i] > sufMin), then we can first reach the same positions that i+1 can reach, making ans[i] = ans[i+1]. Otherwise, we're limited to preMax[i].

This dynamic programming approach efficiently computes the answer by maintaining the prefix maximum array and suffix minimum value, avoiding redundant calculations of reachable positions.

Solution Approach

The solution uses dynamic programming with prefix maximum and suffix minimum tracking. Here's the step-by-step implementation:

1. Initialize Data Structures:

• Create an answer array ans of size n initialized with zeros
• Create a prefix maximum array pre_max where pre_max[i] stores the maximum value from index 0 to i
• Initialize a suffix minimum variable suf_min to infinity

2. Build Prefix Maximum Array:

pre_max = [nums[0]] * n
for i in range(1, n):
    pre_max[i] = max(pre_max[i - 1], nums[i])

This ensures pre_max[i] contains the maximum value in the range [0, i].

3. Process from Right to Left: Starting from the last index and moving backwards:

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])

4. Decision Logic at Each Position:

• If pre_max[i] > suf_min: This means we can create a beneficial jumping pattern:

  • Jump forward from i to where suf_min is located (valid since suf_min < nums[i])
  • From there, jump backward to where pre_max[i] is located (valid since pre_max[i] > suf_min)
  • Continue with the same jumping possibilities as position i + 1
  • Therefore, ans[i] = ans[i + 1]

• If pre_max[i] ≤ suf_min: We cannot create the beneficial pattern, so the best we can reach is pre_max[i] itself

5. Update Suffix Minimum: After processing position i, update suf_min = min(suf_min, nums[i]) to maintain the minimum value seen so far from the right.

Time Complexity: O(n) - Two passes through the array Space Complexity: O(n) - For the pre_max and ans arrays

The algorithm cleverly avoids explicitly tracking all possible jump sequences by recognizing that the maximum reachable value depends on whether we can establish a specific jumping pattern between the prefix maximum and suffix minimum.

Example Walkthrough

Let's walk through the solution with nums = [5, 2, 7, 1, 4].

Step 1: Build prefix maximum array

• pre_max[0] = 5 (max from index 0 to 0)
• pre_max[1] = max(5, 2) = 5 (max from index 0 to 1)
• pre_max[2] = max(5, 7) = 7 (max from index 0 to 2)
• pre_max[3] = max(7, 1) = 7 (max from index 0 to 3)
• pre_max[4] = max(7, 4) = 7 (max from index 0 to 4)

So pre_max = [5, 5, 7, 7, 7]

Step 2: Process from right to left

Index 4 (nums[4] = 4):

• suf_min = ∞
• pre_max[4] = 7 > suf_min = ∞? No
• ans[4] = pre_max[4] = 7
• Update: suf_min = min(∞, 4) = 4

Index 3 (nums[3] = 1):

• suf_min = 4
• pre_max[3] = 7 > suf_min = 4? Yes
• ans[3] = ans[4] = 7
• Update: suf_min = min(4, 1) = 1

Index 2 (nums[2] = 7):

• suf_min = 1
• pre_max[2] = 7 > suf_min = 1? Yes
• ans[2] = ans[3] = 7
• Update: suf_min = min(1, 7) = 1

Index 1 (nums[1] = 2):

• suf_min = 1
• pre_max[1] = 5 > suf_min = 1? Yes
• ans[1] = ans[2] = 7
• Update: suf_min = min(1, 2) = 1

Index 0 (nums[0] = 5):

• suf_min = 1
• pre_max[0] = 5 > suf_min = 1? Yes
• ans[0] = ans[1] = 7
• Update: suf_min = min(1, 5) = 1

Final Result: ans = [7, 7, 7, 7, 7]

Verification for index 0: Starting at index 0 (value 5), we can:

1. Jump forward to index 3 (value 1, which is < 5) ✓
2. From index 3, jump backward to index 2 (value 7, which is > 1) ✓
3. We've reached value 7, the maximum possible!

The algorithm correctly identifies that when pre_max[i] > suf_min, we can create a jumping pattern that reaches the maximum value in the array.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of three main parts:

• First loop (lines 5-6): Iterates through the array once to build the pre_max array, performing O(1) operations per iteration → O(n)
• Second loop (lines 8-10): Iterates through the array once in reverse, performing O(1) operations per iteration → O(n)
• Total: O(n) + O(n) = O(n)

Space Complexity: O(n)

The algorithm uses the following additional space:

• ans array of size n → O(n)
• pre_max array of size n → O(n)
• suf_min variable → O(1)
• Total: O(n) + O(n) + O(1) = O(n)

Where n is the length of the array nums.

Common Pitfalls

1. Incorrect Handling of the Last Element

The provided code has a bug when processing the last element (index n-1). When i = n-1, there's no element to the right, so we cannot jump forward. The code incorrectly sets ans[n-1] = 0 when pre_max[i] > suf_min, but it should be pre_max[n-1] (which equals nums[n-1] for the last element).

Problematic Code:

if i + 1 < n:
    ans[i] = ans[i + 1] if pre_max[i] > suf_min else pre_max[i]
else:
    ans[i] = pre_max[i] if pre_max[i] <= suf_min else 0  # Bug: returns 0

Corrected Code:

if i + 1 < n:
    ans[i] = ans[i + 1] if pre_max[i] > suf_min else pre_max[i]
else:
    ans[i] = pre_max[i]  # Last element can only reach itself or earlier max

2. Misunderstanding the Jump Logic

A common misconception is thinking that pre_max[i] > suf_min directly enables a jump. Actually, this condition checks if there exists a valid jumping sequence:

• From position i, we can potentially jump forward to some position j > i where nums[j] < nums[i]
• From that position j, we might jump backward to reach pre_max[i]
• The condition ensures such a sequence exists somewhere in the suffix

Correct Understanding:

• suf_min represents the minimum value to the right of i
• If pre_max[i] > suf_min, we know there's at least one position to the right with a value smaller than the maximum we've seen so far
• This enables a forward-backward jump pattern to reach higher values

3. Off-by-One Error in Suffix Minimum Update

The suffix minimum should be updated AFTER processing the current position, not before. The current implementation is correct, but moving the update line could break the logic:

Wrong Order:

for i in range(n - 1, -1, -1):
    suf_min = min(suf_min, nums[i])  # Wrong: updates before using
    ans[i] = ans[i + 1] if pre_max[i] > suf_min else pre_max[i]

Correct Order:

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])  # Correct: updates after using

Complete Corrected Solution:

class Solution:
    def maxValue(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
      
        # Build prefix maximum array
        pre_max = [nums[0]] * n
        for i in range(1, n):
            pre_max[i] = max(pre_max[i - 1], nums[i])
      
        suf_min = float('inf')
      
        # Process from right to left
        for i in range(n - 1, -1, -1):
            if i + 1 < n:
                # Can potentially jump forward and utilize future possibilities
                ans[i] = ans[i + 1] if pre_max[i] > suf_min else pre_max[i]
            else:
                # Last element: maximum reachable is pre_max[i]
                ans[i] = pre_max[i]
          
            # Update suffix minimum after processing current position
            suf_min = min(suf_min, nums[i])
      
        return ans