LeetCode Problem 3904

Difficulty: 🟡 Medium
Topics: Array, Prefix Sum

Solution

Problem Understanding

The problem gives an integer array nums of length n and an integer k. For every index i, we split the array into two overlapping parts:

• The prefix nums[0..i]
• The suffix nums[i..n-1]

For that index, we compute an instability score:

$$\text{instability}(i)=\max(nums[0..i])-\min(nums[i..n-1])$$

An index is considered stable if this value is less than or equal to k. Among all stable indices, we must return the smallest one. If no index satisfies the condition, we return -1.

The input array can contain up to 10^5 elements, and values may be as large as 10^9. These constraints immediately tell us that quadratic algorithms are too slow. Any solution that repeatedly scans prefixes or suffixes for every index would require roughly 10^10 operations in the worst case, which is impractical.

Several edge cases are important:

• The array may contain only one element. In that case, the maximum and minimum are the same element, so the instability score is always zero.
• No stable index may exist, requiring a return value of -1.
• The first index could already be stable, so we must stop as soon as we find the smallest valid index.
• Arrays with repeated values should be handled correctly.
• Very large numbers require care, although both Python and Go integer types are sufficient for this problem.

Approaches

Brute Force

The most direct approach is to examine every index independently.

For index i, we compute:

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

Then we calculate their difference and check whether it is at most k.

This approach is correct because it follows the definition exactly. However, finding a maximum and minimum from scratch for every index requires scanning portions of the array repeatedly. In the worst case, this leads to quadratic complexity.

Key Observation

The expensive part is recomputing prefix maxima and suffix minima over and over.

Notice that:

• The maximum of a prefix can be built incrementally from left to right.
• The minimum of a suffix can be built incrementally from right to left.

If we precompute:

• prefix_max[i] = max(nums[0..i])
• suffix_min[i] = min(nums[i..n-1])

then the instability score at index i becomes

$$prefix_max[i]-suffix_min[i]$$

which can be evaluated in constant time.

Thus, after linear preprocessing, we only need one more linear scan to find the first stable index.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Recomputes prefix maximum and suffix minimum for every index
Optimal	O(n)	O(n)	Precomputes prefix maxima and suffix minima once

Algorithm Walkthrough

1. Create the prefix maximum array

Traverse from left to right.

For each position i, store the largest value seen so far. This gives:

prefix_max[i] = max(nums[0], ..., nums[i])

This avoids repeatedly searching the prefix.

2. Create the suffix minimum array

Traverse from right to left.

For each position i, store the smallest value encountered from i to the end:

suffix_min[i] = min(nums[i], ..., nums[n-1])

This prevents repeatedly scanning suffixes.

3. Evaluate every index

For each index i, compute

$$\text{instability}=prefix_max[i]-suffix_min[i]$$

If the instability is at most k, return i immediately.

Because indices are checked from left to right, the first valid index is automatically the smallest stable index.

4. Return -1 if necessary

If the scan finishes without finding a valid index, then no stable index exists.

Why it works

The key invariant is that:

• prefix_max[i] always equals the maximum element in nums[0..i].
• suffix_min[i] always equals the minimum element in nums[i..n-1].

Therefore their difference is exactly the instability score defined in the problem. Since indices are examined in increasing order, the first index whose score does not exceed k is necessarily the smallest stable index.

Python Solution

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

        prefix_max = [0] * n
        suffix_min = [0] * n

        prefix_max[0] = nums[0]
        for i in range(1, n):
            prefix_max[i] = max(prefix_max[i - 1], nums[i])

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

        for i in range(n):
            if prefix_max[i] - suffix_min[i] <= k:
                return i

        return -1

The implementation begins by allocating two arrays of size n.

The first loop constructs prefix_max. Each position inherits the previous maximum and compares it with the current element.

The second loop constructs suffix_min. Starting from the end, each position inherits the minimum from the right and compares it with the current value.

Finally, a third loop computes the instability score for every index. As soon as a score less than or equal to k is encountered, that index is returned. If none satisfy the condition, the function returns -1.

Go Solution

func firstStableIndex(nums []int, k int) int {
	n := len(nums)

	prefixMax := make([]int, n)
	suffixMin := make([]int, n)

	prefixMax[0] = nums[0]
	for i := 1; i < n; i++ {
		if nums[i] > prefixMax[i-1] {
			prefixMax[i] = nums[i]
		} else {
			prefixMax[i] = prefixMax[i-1]
		}
	}

	suffixMin[n-1] = nums[n-1]
	for i := n - 2; i >= 0; i-- {
		if nums[i] < suffixMin[i+1] {
			suffixMin[i] = nums[i]
		} else {
			suffixMin[i] = suffixMin[i+1]
		}
	}

	for i := 0; i < n; i++ {
		if prefixMax[i]-suffixMin[i] <= k {
			return i
		}
	}

	return -1
}

The Go implementation follows exactly the same logic as the Python version.

Slices are used to store the prefix maximum and suffix minimum arrays. Since the problem guarantees at least one element, no special handling for empty arrays is required. Integer values are well within Go's int range on modern platforms, so overflow is not a concern.

Worked Examples

Example 1

Input:

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

Prefix maxima

i	nums[i]	prefix_max[i]
0	5	5
1	0	5
2	1	5
3	4	5

Suffix minima

i	nums[i]	suffix_min[i]
3	4	4
2	1	1
1	0	0
0	5	0

Thus:

i	prefix_max	suffix_min	instability
0	5	0	5
1	5	0	5
2	5	1	4
3	5	4	1

Index 3 is the first with instability ≤ 3.

Answer:

3

Example 2

Input:

nums = [3,2,1]
k = 1

Prefix maxima:

i	prefix_max
0	3
1	3
2	3

Suffix minima:

i	suffix_min
0	1
1	1
2	1

Instability values:

i	instability
0	2
1	2
2	2

All values exceed 1, so the answer is:

-1

Example 3

Input:

nums = [0]
k = 0

Prefix maximum:

i	prefix_max
0	0

Suffix minimum:

i	suffix_min
0	0

Instability:

i	instability
0	0

Since 0 ≤ 0, the answer is:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Three linear passes through the array
Space	O(n)	Two auxiliary arrays store prefix maxima and suffix minima

The algorithm performs one left-to-right traversal, one right-to-left traversal, and one final scan. Each element is processed a constant number of times, giving linear time complexity. The additional memory usage comes from the two arrays used to store intermediate information.

Test Cases

sol = Solution()

assert sol.firstStableIndex([5, 0, 1, 4], 3) == 3      # example 1
assert sol.firstStableIndex([3, 2, 1], 1) == -1        # example 2
assert sol.firstStableIndex([0], 0) == 0               # single element

assert sol.firstStableIndex([1, 1, 1], 0) == 0         # all equal
assert sol.firstStableIndex([1, 2, 3, 4], 0) == 3      # increasing array
assert sol.firstStableIndex([4, 3, 2, 1], 0) == -1     # decreasing array
assert sol.firstStableIndex([4, 3, 2, 1], 3) == 0      # first index stable
assert sol.firstStableIndex([10], 100) == 0            # single large value
assert sol.firstStableIndex([7, 1, 6, 2, 5], 4) == 0   # threshold exactly met
assert sol.firstStableIndex([7, 1, 6, 2, 5], 3) == 4   # later stable index
assert sol.firstStableIndex([10**9, 0, 10**9], 10**9) == 0  # very large values

Test Summary

Test	Why
[5,0,1,4], 3	Provided example
[3,2,1], 1	No stable index
[0], 0	Single element
[1,1,1], 0	Duplicate values
[1,2,3,4], 0	Strictly increasing array
[4,3,2,1], 0	Strictly decreasing array
[4,3,2,1], 3	Earliest index is valid
[10]	Single large number
[7,1,6,2,5], 4	Instability equals threshold
[7,1,6,2,5], 3	Stable index appears later
Large values	Confirms handling of 10^9

Edge Cases

Single-element arrays

When the array contains exactly one element, the prefix and suffix both consist of that same element. Their maximum and minimum are identical, so the instability score is always zero. The implementation handles this naturally because both auxiliary arrays contain one entry.

No stable index exists

Some arrays never produce an instability score less than or equal to k. A common mistake is to return the last index examined instead of -1. The implementation avoids this by returning only when a valid index is found and otherwise returning -1 after the entire scan finishes.

The earliest index is already stable

It is possible that index 0 satisfies the condition. Since the final scan proceeds from left to right and returns immediately when it encounters a valid index, the algorithm correctly returns the smallest stable index instead of continuing unnecessarily.

Strictly increasing arrays

In an increasing array, the suffix minimum at position i equals nums[i], while the prefix maximum equals the largest element seen so far. Depending on k, the first stable index may be near the end. The algorithm computes these values efficiently and avoids repeatedly scanning the array.

Arrays containing duplicate values

Repeated numbers can sometimes expose errors in comparison logic. Since the algorithm uses standard max and min operations and stores exact prefix and suffix extrema, duplicate values are handled correctly without any special cases.