3904. Smallest Stable Index II

MediumArrayPrefix Sum

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

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

For each index i, we define an instability score based on two values:

max(nums[0..i]) — the largest value among the elements from index 0 to index i (inclusive).
min(nums[i..n - 1]) — the smallest value among the elements from index i to index n - 1 (inclusive).

The instability score of index i is the difference between these two values:

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

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

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

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

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Prefix Sums?

This problem maps to Prefix Sums through a short path in the full flowchart.

Precomputing prefix sums answers range queries in constant time.

Open in Flowchart

Intuition

The most direct way to solve this problem is to compute the instability score for every index i and check whether it is less than or equal to k. However, if we naively recalculate max(nums[0..i]) and min(nums[i..n - 1]) from scratch for each index, the work repeats and becomes inefficient.

The key observation is that both quantities have a nice monotonic, incremental structure as we scan through the array:

max(nums[0..i]) is a prefix maximum. As i increases from left to right, the maximum can only stay the same or grow. So we can maintain it with a single running variable left, updating it by left = max(left, nums[i]) at each step.
min(nums[i..n - 1]) is a suffix minimum. For a fixed index i, it depends on all elements to its right, so it is convenient to precompute it ahead of time by scanning from right to left and storing the result in an array right, where right[i] holds the smallest value from index i to the end.

Once we have the suffix minimum right ready, we only need a single forward pass through the array. At each index i, the running prefix maximum gives us max(nums[0..i]), and right[i] gives us min(nums[i..n - 1]). Their difference is exactly the instability score, which we compare against k.

Because we want the smallest stable index, we scan from left to right and return immediately the first index whose instability score is <= k. If the loop completes without finding any such index, no stable index exists, so we return -1.

This combination of precomputing the suffix minimum and maintaining a running prefix maximum lets us answer the question in a single clean traversal after the preprocessing step.

Pattern Learn more about Prefix Sum patterns.

Solution Approach

Solution 1: Preprocessing + Enumeration

We follow a two-phase strategy: first preprocess the suffix minimums, then enumerate each index while maintaining the prefix maximum.

Step 1: Preprocess the suffix minimum array right.

We build an array right of length n, where right[i] represents the minimum value among the elements in nums from index i to index n - 1.

Initialize every entry to nums[-1], the last element.
Traverse nums from back to front, starting at index n - 2 down to 0. At each step, set right[i] = min(right[i + 1], nums[i]).

This works because the minimum of the suffix starting at i is simply the smaller of the current element nums[i] and the minimum of the suffix starting at i + 1, which we have already computed.

Step 2: Enumerate from front to back while tracking the prefix maximum.

We maintain a variable left, which represents max(nums[0..i]), the largest value seen from index 0 up to the current index i.

For each index i with value x, update left = max(left, x).
Compute the instability score as left - right[i].
If left - right[i] <= k, then index i is stable, and since we are scanning left to right, this is the smallest stable index — return i immediately.

If the loop finishes without returning, no stable index exists, so we return -1.

Data structures and patterns used:

A suffix minimum array (right) computed in a backward pass.
A running prefix maximum (left) maintained in a forward pass.
Early return to capture the smallest qualifying index.

Complexity Analysis:

Time complexity: O(n), where n is the length of nums. The backward pass to build right takes O(n), and the forward pass to find the answer also takes O(n).
Space complexity: O(n), due to the extra right array storing the suffix minimums.

Example Walkthrough

Let's trace through the solution approach with a small concrete example.

Input: nums = [3, 1, 4, 2], k = 1, so n = 4.

We want the smallest index i where max(nums[0..i]) - min(nums[i..n - 1]) <= 1.

Step 1: Build the suffix minimum array right.

right[i] holds the minimum from index i to the end. We initialize right[3] = nums[3] = 2, then fill from right to left using right[i] = min(right[i + 1], nums[i]).

`i`	`nums[i]`	Computation	`right[i]`
3	2	base case	2
2	4	`min(right[3], 4) = min(2, 4)`	2
1	1	`min(right[2], 1) = min(2, 1)`	1
0	3	`min(right[1], 3) = min(1, 3)`	1

Resulting array: right = [1, 1, 2, 2].

Step 2: Forward pass maintaining the prefix maximum left.

We start with left = -∞ (or the first element). At each index, update left = max(left, nums[i]), compute instability = left - right[i], and check against k = 1.

`i`	`nums[i]`	`left = max(...)`	`right[i]`	`instability = left - right[i]`	`<= k`?
0	3	3	1	`3 - 1 = 2`	No (2 > 1)
1	1	3	1	`3 - 1 = 2`	No (2 > 1)
2	4	4	2	`4 - 2 = 2`	No (2 > 1)
3	2	4	2	`4 - 2 = 2`	No (2 > 1)

The loop completes without finding a stable index, so we return -1.

A contrasting case (where an answer exists):

Take nums = [3, 1, 4, 2] but now k = 2. The right array is unchanged: [1, 1, 2, 2].

`i`	`left`	`right[i]`	`instability`	`<= k = 2`?
0	3	1	`2`	Yes

At index 0, the instability score is 2, which satisfies 2 <= 2. Since we scan left to right and return on the first match, we immediately return 0 — the smallest stable index.

Key takeaways from the trace:

The right array is computed once in a single backward sweep, so each suffix minimum is ready before the forward scan begins.
During the forward scan, left is non-decreasing (it only grows or stays the same), confirming the prefix-maximum property.
The early return guarantees we capture the smallest qualifying index without scanning the rest of the array.

Solution Implementation

1class Solution:
2    def firstStableIndex(self, nums: list[int], k: int) -> int:
3        n = len(nums)
4
5        # suffix_min[i] = minimum value in nums[i..n-1]
6        suffix_min = [nums[-1]] * n
7        for i in range(n - 2, -1, -1):
8            suffix_min[i] = min(suffix_min[i + 1], nums[i])
9
10        # prefix_max tracks the maximum value in nums[0..i] as we iterate
11        prefix_max = 0
12        for i, x in enumerate(nums):
13            prefix_max = max(prefix_max, x)
14            # Check whether the gap between the prefix max and suffix min
15            # at index i is within the allowed threshold k
16            if prefix_max - suffix_min[i] <= k:
17                return i
18
19        # No index satisfies the condition
20        return -1
21

1class Solution {
2    public int firstStableIndex(int[] nums, int k) {
3        int n = nums.length;
4
5        // suffixMin[i] holds the minimum value among nums[i..n-1].
6        // This lets us query the smallest element to the right of (and including) index i in O(1).
7        int[] suffixMin = new int[n];
8        suffixMin[n - 1] = nums[n - 1];
9
10        // Build the suffix minimum array from right to left.
11        for (int i = n - 2; i >= 0; i--) {
12            suffixMin[i] = Math.min(suffixMin[i + 1], nums[i]);
13        }
14
15        // prefixMax tracks the maximum value among nums[0..i] as we scan left to right.
16        int prefixMax = 0;
17        for (int i = 0; i < n; i++) {
18            // Update the running maximum of the prefix ending at index i.
19            prefixMax = Math.max(prefixMax, nums[i]);
20
21            // If the spread between the prefix maximum and the suffix minimum
22            // (from i onward) is within the allowed threshold k, index i is stable.
23            if (prefixMax - suffixMin[i] <= k) {
24                return i;
25            }
26        }
27
28        // No index satisfies the stability condition.
29        return -1;
30    }
31}
32

1class Solution {
2public:
3    int firstStableIndex(vector<int>& nums, int k) {
4        int n = nums.size();
5
6        // suffixMin[i] holds the minimum value of nums[i..n-1]
7        vector<int> suffixMin(n);
8        suffixMin[n - 1] = nums[n - 1];
9
10        // Build the suffix minimum array from right to left
11        for (int i = n - 2; i >= 0; --i) {
12            suffixMin[i] = min(suffixMin[i + 1], nums[i]);
13        }
14
15        // prefixMax tracks the maximum value of nums[0..i] as we iterate
16        int prefixMax = 0;
17        for (int i = 0; i < n; ++i) {
18            // Update the running prefix maximum to include the current element
19            prefixMax = max(prefixMax, nums[i]);
20
21            // If the gap between the prefix maximum and the suffix minimum
22            // at this index is within k, this is the first stable index
23            if (prefixMax - suffixMin[i] <= k) {
24                return i;
25            }
26        }
27
28        // No index satisfies the stability condition
29        return -1;
30    }
31};
32

1/**
2 * Finds the first index `i` such that the difference between the maximum value
3 * in the prefix nums[0..i] and the minimum value in the suffix nums[i..n-1]
4 * is less than or equal to `k`.
5 *
6 * @param nums - The input array of numbers.
7 * @param k - The allowed maximum difference threshold.
8 * @returns The first qualifying index, or -1 if none exists.
9 */
10function firstStableIndex(nums: number[], k: number): number {
11    const length: number = nums.length;
12
13    // suffixMin[i] holds the minimum value of nums[i..length-1].
14    const suffixMin: number[] = new Array<number>(length);
15
16    // The minimum of the last element is the element itself.
17    suffixMin[length - 1] = nums[length - 1];
18
19    // Build the suffix minimum array from right to left.
20    for (let i = length - 2; i >= 0; i--) {
21        suffixMin[i] = Math.min(suffixMin[i + 1], nums[i]);
22    }
23
24    // prefixMax tracks the maximum value of nums[0..i] as we iterate.
25    let prefixMax: number = 0;
26
27    // Scan from left to right, updating the running prefix maximum.
28    for (let i = 0; i < length; i++) {
29        prefixMax = Math.max(prefixMax, nums[i]);
30
31        // If the gap between the prefix max and the suffix min is within k,
32        // this index is the first stable index.
33        if (prefixMax - suffixMin[i] <= k) {
34            return i;
35        }
36    }
37
38    // No index satisfies the condition.
39    return -1;
40}
41

Time and Space Complexity

Time Complexity: O(n)

The code consists of two separate loops, each iterating over the array once:

The first loop runs from i = n - 2 down to 0, computing the suffix minimum array right. This takes O(n) time.
The second loop iterates through all elements of nums using enumerate, maintaining a running prefix maximum left and performing a constant-time comparison left - right[i] <= k at each step. This also takes O(n) time.

Since the two loops run sequentially, the total time complexity is O(n) + O(n) = O(n), where n is the length of the nums array.

Space Complexity: O(n)

The algorithm allocates an auxiliary array right of size n to store the suffix minimum values, which requires O(n) extra space. All other variables (left, i, x, n) use constant O(1) space. Therefore, the overall space complexity is O(n), where n is the length of the nums array.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Initializing `prefix_max` to `0` instead of `-infinity`

The most subtle and dangerous bug in this code is the initialization:

prefix_max = 0

This assumes that all elements in nums are non-negative. However, the problem only states that nums is an integer array — it may contain negative numbers.

Why this breaks:

Consider nums = [-5, -3, -8] with k = 0.

The true max(nums[0..0]) should be -5.
But because prefix_max starts at 0, after the first update we get prefix_max = max(0, -5) = 0, which is wrong.
This inflates the prefix maximum, making prefix_max - suffix_min[i] artificially large and potentially causing valid stable indices to be missed (returning -1 incorrectly).

Solution:

Initialize prefix_max to negative infinity so the first real element always sets it correctly:

class Solution:
    def firstStableIndex(self, nums: list[int], k: int) -> int:
        n = len(nums)

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

        prefix_max = float('-inf')   # safe for negative numbers
        for i, x in enumerate(nums):
            prefix_max = max(prefix_max, x)
            if prefix_max - suffix_min[i] <= k:
                return i

        return -1

Alternatively, you can seed prefix_max = nums[0] before the loop, since the first element is always included in every prefix.

Pitfall 2: Not handling an empty input array

The line:

suffix_min = [nums[-1]] * n

will throw an IndexError if nums is empty (nums[-1] fails on an empty list).

Solution:

Add an early guard at the top of the function:

if not nums:
    return -1

Pitfall 3: Misreading the index ranges (off-by-one in the two windows)

It is easy to confuse the two windows because they overlap at index i:

max(nums[0..i]) is inclusive of i.
min(nums[i..n-1]) is also inclusive of i.

A common mistake is to compute the suffix minimum as min(nums[i+1..n-1]) (excluding i), or to update prefix_max after the comparison instead of before. Both errors shift the windows incorrectly.

Solution:

Always update prefix_max with the current element before checking the condition, and ensure suffix_min[i] includes nums[i]. The order in the loop matters:

prefix_max = max(prefix_max, x)   # include current i FIRST
if prefix_max - suffix_min[i] <= k:   # then compare
    return i

This guarantees both windows correctly include index i, matching the problem definition.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know

3904. Smallest Stable Index II

Problem Description

How We Pick the Algorithm

Why Prefix Sums?

Intuition

Solution Approach

Solution 1: Preprocessing + Enumeration

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

Pitfall 1: Initializing prefix_max to 0 instead of -infinity

Pitfall 2: Not handling an empty input array

Pitfall 3: Misreading the index ranges (off-by-one in the two windows)

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Recommended Readings

Pitfall 1: Initializing `prefix_max` to `0` instead of `-infinity`