You are given an integer array nums of length n and an integer k.

For each index i, we define an instability score that measures how "unstable" that position is. The instability score at index i is calculated as:

max(nums[0..i]) - min(nums[i..n - 1])

Let's break down what each part means:

• max(nums[0..i]) is the largest value among all elements from index 0 up to and including index i. In other words, it's the maximum of the prefix ending at i.
• min(nums[i..n - 1]) is the smallest value among all elements from index i up to and including the last index n - 1. In other words, it's the minimum of the suffix starting at i.

The instability score is the difference between these two values: the maximum of the left part (including i) minus the minimum of the right part (including i).

An index i is called stable if its instability score is less than or equal to k. That is, index i is stable when:

max(nums[0..i]) - min(nums[i..n - 1]) <= k

Your task is to find the smallest index i that is stable, and return it. If there is no index that satisfies the stability condition, return -1.

The key observation is that the instability score at index i depends on two separate quantities: the maximum of the prefix nums[0..i] and the minimum of the suffix nums[i..n - 1]. If we could quickly know both values for every index i, we could simply check each index and return the first one that satisfies the condition.

Computing the prefix maximum for each i is easy: as we move from left to right, the maximum of nums[0..i] only grows or stays the same. We can keep a running variable left that tracks the largest value seen so far, updating it with left = max(left, nums[i]) at each step.

The suffix minimum is trickier to compute on the fly while scanning from left to right, because at index i we would need to know the minimum of all elements from i to the end—values we haven't "looked at" yet in a left-to-right pass. The natural fix is to precompute these suffix minimums in advance. By traversing nums from back to front, we can build an array right, where right[i] stores the minimum value among nums[i..n - 1]. Each entry is computed using right[i] = min(right[i + 1], nums[i]), since the minimum of a suffix is just the current element compared against the minimum of the suffix one position to its right.

Once we have the right array ready, we make a single left-to-right pass. At each index i, the prefix maximum is available in left, and the suffix minimum is available in right[i]. The instability score is simply left - right[i]. Because we want the smallest stable index, we check this condition as we go and return immediately the first time it holds, guaranteeing the earliest qualifying index. If the entire scan finishes without finding any stable index, we return -1.

Pattern Learn more about Prefix Sum patterns.

Solution 1: Preprocessing + Enumeration

This solution combines a preprocessing step (suffix minimum array) with a single enumeration pass to find the answer efficiently.

Step 1: Preprocess the suffix minimum array right.

We create an array right of length n, where right[i] represents the minimum value among the elements nums[i..n - 1]. We initialize every entry to nums[-1] (the last element), since the suffix that starts at the last index contains only that one element.

Then we traverse nums from back to front, starting at index n - 2 and going down to 0:

right = [nums[-1]] * n
for i in range(n - 2, -1, -1):
    right[i] = min(right[i + 1], nums[i])

The recurrence right[i] = min(right[i + 1], nums[i]) works because the minimum of the suffix starting at i is just the current element nums[i] compared against the already-known minimum of the suffix starting at i + 1.

Step 2: Enumerate each index from left to right.

We maintain a variable left, initialized to 0, which tracks max(nums[0..i])—the maximum value seen so far in the prefix. As we iterate over each index i with value x, we update left using left = max(left, x).

At every index i, both pieces of the instability score are now available:

• The prefix maximum is held in left.
• The suffix minimum is held in right[i].

So the instability score is simply left - right[i]. If this value is <= k, index i is stable, and since we are scanning left to right, it must be the smallest such index, so we return it immediately:

left = 0
for i, x in enumerate(nums):
    left = max(left, x)
    if left - right[i] <= k:
        return i
return -1

If the loop completes without finding any stable index, we return -1.

Complexity Analysis:

• Time complexity: O(n). We make one backward pass to build the right array and one forward pass to check each index, both linear in the length of nums.
• Space complexity: O(n), due to the extra right array storing the suffix minimums. The left variable uses only constant additional space.

The pattern here is the classic prefix/suffix preprocessing technique: when a per-index query depends on information from both directions, precompute one direction in an auxiliary array and stream the other direction with a running variable, reducing what could be an O(n^2) brute force into a clean O(n) solution.