3903. Smallest Stable Index I

Array
Prefix Sum
Prefix Maximum
Suffix Minimum

TIME

O(n)

SPACE

O(n)

Intuition

The score at index i needs two aggregates that both extend over ranges, but each is monotone as i moves:

max(nums[0..i]) only ever grows as i increases, a running prefix maximum.
min(nums[i..n-1]) only ever grows as i increases too, a suffix minimum, computed right to left.

Neither needs to be recomputed per index. Two linear passes give every score in O(1), so the whole thing is a single sweep afterwards.

Approach

Build prefMax[i] = max(nums[0..i]) in a left-to-right pass.
Build sufMin[i] = min(nums[i..n-1]) in a right-to-left pass.
Scan i from 0 upward and return the first index where prefMax[i] - sufMin[i] <= k.
If no index qualifies, return -1.

Scanning left to right returns the smallest qualifying index automatically.

Complexity

Time: O(n), two aggregate passes plus one scan
Space: O(n), the two arrays (reducible to O(n) for just the suffix array, with the prefix max kept as a running scalar)

Edge Cases

Single element → prefMax == sufMin == nums[0], score 0, so index 0 is stable whenever k >= 0 (Example 3)
No stable index → -1 (Example 2)
Both ranges are inclusive of i and overlap at that element, so the score is never negative
Values up to 10^9 and k up to 10^9; the difference fits in a signed 32-bit int
The score is not monotone in i, so the first qualifying index must be found by scanning, not by binary search

Code

from typing import List


class Solution:
    def smallestStableIndex(self, nums: List[int], k: int) -> int:
        """
        3903. Smallest Stable Index I
        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

/**
 * 3903. Smallest Stable Index I
 * 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;
    }
}