3660. Jump Game IX

Time: O(n)

Space: O(n)

Problem Overview

For each position i, the maximum collectible value depends on whether the best value seen so far (the prefix maximum) is still "reachable" given what lies ahead.

Intuition

For each position i, the maximum collectible value depends on whether the best value seen so far (the prefix maximum) is still "reachable" given what lies ahead. If a smaller element in the suffix would block advancement, the prefix max is the ceiling; otherwise the answer from the next position carries forward. A single right-to-left pass with a running suffix minimum resolves this in O(n).

Algorithm

1Build prefixMax: prefixMax[i] = max(nums[0..i]).
2Initialise suffixMin = +8 and result array of length n.
3Traverse i from n-1 down to 0.
4If prefixMax[i] > suffixMin: result[i] = result[i+1] (or 0 if i is the last index).
5Otherwise: result[i] = prefixMax[i].
6Update suffixMin = min(suffixMin, nums[i]) before moving left.

Example Walkthrough

Input: nums = [3, 1, 5, 2, 4]

1.prefixMax = [3, 3, 5, 5, 5].
2.i=4: suffixMin=8, 5>8? No ? result[4]=5. suffixMin=4.
3.i=3: 5>4? Yes ? result[3]=result[4]=5. suffixMin=min(4,2)=2.
4.i=2: 5>2? Yes ? result[2]=result[3]=5. suffixMin=min(2,5)=2.
5.i=1: 3>2? Yes ? result[1]=result[2]=5. suffixMin=min(2,1)=1.
6.i=0: 3>1? Yes ? result[0]=result[1]=5. suffixMin=min(1,3)=1.
7.Result: [5, 5, 5, 5, 5].

Output: [5, 5, 5, 5, 5]

Common Pitfalls

•Don't skip the modulo when there is no modulo needed here � but do handle the last index (i+1 < n) before reading result[i+1].
•The prefix max must be computed as a full array first; you cannot compute it on the fly in the right-to-left pass.
•suffixMin must be updated after reading result[i], not before, to avoid including nums[i] in its own suffix.

3660.cs

// Approach: Build a prefix-max array, then sweep right-to-left maintaining a suffix minimum.
// At each position, if the prefix max exceeds the suffix min, the optimal value propagates from result[i+1];
// otherwise the best value is capped at the prefix max seen so far.
// Time: O(n) Space: O(n)

public class Solution
{
    public int[] MaxValue(int[] nums)
    {
        int n = nums.Length;
        int[] result = new int[n];

        // Build prefix maximum array
        // prefixMax[i] stores the maximum value from nums[0] to nums[i]
        int[] prefixMax = new int[n];
        prefixMax[0] = nums[0];
        for (int i = 1; i < n; i++)
            prefixMax[i] = Math.Max(prefixMax[i - 1], nums[i]);

        // Initialize suffix minimum with a large value (approximately int.MaxValue)
        int suffixMin = 1 << 30;

        // Traverse from right to left to compute result
        // For each position, check if prefix maximum is greater than suffix minimum
        for (int i = n - 1; i >= 0; i--)
        {
            // If prefix max up to current position is greater than suffix min after current position,
            // use the next result value (or 0 for last element)
            // Otherwise, use the prefix max value
            if (prefixMax[i] > suffixMin)
                result[i] = (i + 1 < n) ? result[i + 1] : 0;
            else
                result[i] = prefixMax[i];

            // Update suffix minimum to include current element
            suffixMin = Math.Min(suffixMin, nums[i]);
        }

        return result;
    }
}

Was this solution helpful?