3904. Smallest Stable Index II

Array
Prefix Sum
Prefix Maximum
Suffix Minimum

TIME

O(n)

SPACE

O(n)

Intuition

Identical to part I; only the input size grows (n from 100 to 10^5), which rules out recomputing max and min per index, that would be O(n^2) and roughly 10^10 operations. The linear formulation already handles it.

Both aggregates are monotone as i advances:

max(nums[0..i]) only grows, a running prefix maximum, maintained in O(1) per step.
min(nums[i..n-1]) only grows too, but is computed from the right, a suffix minimum array.

So one backward pass and one forward pass give every score in O(1) each.

Approach

Build sufMin[i] = min(nums[i..n-1]) in a right-to-left pass.
Sweep i left to right, maintaining prefMax as a running scalar.
Return the first i where prefMax - sufMin[i] <= k.
If none qualifies, return -1.

Sweeping left to right returns the smallest qualifying index automatically, so no extra comparison is needed.

Complexity

Time: O(n), one suffix pass plus one scan
Space: O(n), the suffix array (the prefix max needs only a scalar)

Edge Cases

Single element → prefMax == sufMin == nums[0], score 0, stable whenever k >= 0 (Example 3)
No stable index → -1 (Example 2)
Both ranges include index i, so they overlap there and the score is never negative
Values and k up to 10^9; the difference stays within signed 32-bit range
The score is not monotone in i, so the first qualifying index must be found by scanning rather than binary search

Code

from typing import List


class Solution:
    def smallestStableIndex(self, nums: List[int], k: int) -> int:
        """
        3904. Smallest Stable Index II
        Time: O(n)
        Space: O(n)
        """
        n = len(nums)

        # suf_min[i] = min(nums[i..n-1])
        suf_min = [0] * n
        suf_min[n - 1] = nums[n - 1]
        for i in range(n - 2, -1, -1):
            suf_min[i] = min(nums[i], suf_min[i + 1])

        # Running prefix max; scanning left to right finds the smallest index.
        pref_max = float("-inf")
        for i in range(n):
            pref_max = max(pref_max, nums[i])
            if pref_max - suf_min[i] <= k:
                return i
        return -1

/**
 * 3904. Smallest Stable Index II
 * Time: O(n)
 * Space: O(n)
 */
class Solution {
    public int smallestStableIndex(int[] nums, int k) {
        int n = nums.length;

        // sufMin[i] = min(nums[i..n-1])
        int[] sufMin = new int[n];
        sufMin[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            sufMin[i] = Math.min(nums[i], sufMin[i + 1]);
        }

        // Running prefix max; scanning left to right finds the smallest index.
        int prefMax = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            prefMax = Math.max(prefMax, nums[i]);
            if (prefMax - sufMin[i] <= k) {
                return i;
            }
        }
        return -1;
    }
}