3660. Jump Game IX

Time: O(n)

Space: O(n)

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 = +∞ 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=∞, 5>∞? 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?