423. Smallest Stable Index II

The instability score at index i only depends on the running maximum of the elements up to i and the running minimum of the elements from i onward. Precompute both with two linear sweeps, then scan left-to-right for the first index whose score is <= k.

Idea

This is the large-input version of Smallest Stable Index — here n can reach 10^5, so the naive approach of recomputing max(nums[0..i]) and min(nums[i..n-1]) from scratch at every index (O(n) per index, O(n^2) overall, up to ~10^10 operations) will time out. We need a linear algorithm.

The instability score at index i is max(nums[0..i]) - min(nums[i..n-1]). Both quantities are running extremes, so precompute them:

• prefixMax[i] = the maximum of nums[0..i]. It satisfies prefixMax[i] = max(prefixMax[i-1], nums[i]), so one left-to-right sweep fills it.
• suffixMin[i] = the minimum of nums[i..n-1]. It satisfies suffixMin[i] = min(suffixMin[i+1], nums[i]), so one right-to-left sweep fills it.

Once both arrays exist, score(i) = prefixMax[i] - suffixMin[i] is an O(1) lookup. Scan indices in increasing order and return the first one with score(i) <= k; if none qualifies, return -1.

Walk-through

Take nums = [5, 0, 1, 4], k = 3.

1. Forward sweep (prefixMax): start with prefixMax[0] = 5. Then max(5,0)=5, max(5,1)=5, max(5,4)=5 -> prefixMax = [5, 5, 5, 5].
2. Backward sweep (suffixMin): start with suffixMin[3] = 4. Then min(4,1)=1, min(1,0)=0, min(0,5)=0 -> suffixMin = [0, 0, 1, 4].
3. Scan for the answer:
   • i=0: 5 - 0 = 5 > 3.
   • i=1: 5 - 0 = 5 > 3.
   • i=2: 5 - 1 = 4 > 3.
   • i=3: 5 - 4 = 1 <= 3 -> stable. Return 3.

Why it is correct

prefixMax is non-decreasing and suffixMin is non-increasing, but the score prefixMax[i] - suffixMin[i] is not monotonic in general, so we cannot binary-search it — we must check indices in order to find the smallest stable one. The two sweeps guarantee every score lookup is exact and O(1). Values fit in a 32-bit int (nums[i] <= 10^9), so no overflow concerns for the subtraction.

Complexity

• Time: O(n) — two sweeps to build the arrays plus one scan. This is what keeps n = 10^5 well within the time limit.
• Space: O(n) — the prefixMax and suffixMin arrays.

class Solution {
    public int firstStableIndex(int[] nums, int k) {
        int n = nums.length;

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

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

        for (int i = 0; i < n; i++) {
            if (prefixMax[i] - suffixMin[i] <= k) {
                return i;
            }
        }
        return -1;
    }
}