LeetCode 3903 - Smallest Stable Index I

The problem asks us to find the smallest index i in an integer array nums such that the instability score at that index is less than or equal to a given integer k. The instability score is defined as the difference between the maximum of the prefix nums[0..

leetcodeeasyarrayprefix-sum

LeetCode Problem 3903

Difficulty: 🟢 Easy
Topics: Array, Prefix Sum

Solution

Problem Understanding

The problem asks us to find the smallest index i in an integer array nums such that the instability score at that index is less than or equal to a given integer k. The instability score is defined as the difference between the maximum of the prefix nums[0..i] and the minimum of the suffix nums[i..n-1]. In other words, for every index i, we compute the largest number seen so far up to i, subtract the smallest number from i to the end of the array, and check if that value is less than or equal to k.

The input nums can have up to 100 elements, each up to 10^9, and k can also be up to 10^9. This guarantees that integer arithmetic will not overflow in most languages like Python, but care is needed in languages with fixed-size integers. The expected output is a single integer representing the first stable index, or -1 if none exist.

Important edge cases include arrays of length 1, arrays where all elements are equal, arrays that are strictly increasing or decreasing, and arrays where no index meets the stability condition.

Approaches

Brute Force Approach

The brute force method is straightforward. For each index i, we compute the maximum of the prefix nums[0..i] and the minimum of the suffix nums[i..n-1], then compute the instability score and check if it is less than or equal to k. If so, we return i. Otherwise, we continue until the end of the array.

This approach is correct because it directly follows the problem definition. However, it is inefficient because for each index we are recomputing maximums and minimums repeatedly, leading to a time complexity of O(n^2). Given the constraints n <= 100, this is feasible but not optimal.

Optimal Approach

The key observation is that we can precompute the prefix maximums and suffix minimums in two linear passes. First, we create an array prefix_max where prefix_max[i] = max(nums[0..i]). Next, we create an array suffix_min where suffix_min[i] = min(nums[i..n-1]). With these two arrays, computing the instability score at any index i is a constant-time operation. This reduces the overall time complexity to O(n), which is optimal for the input size.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Computes max and min for each index independently
Optimal O(n) O(n) Precomputes prefix max and suffix min for constant-time instability checks

Algorithm Walkthrough

  1. Initialize two arrays: prefix_max of length n and suffix_min of length n.

  2. Compute prefix_max by iterating from left to right, setting prefix_max[i] = max(prefix_max[i-1], nums[i]).

  3. Compute suffix_min by iterating from right to left, setting suffix_min[i] = min(suffix_min[i+1], nums[i]).

  4. Iterate over each index i from 0 to n-1:

  5. Compute the instability score as prefix_max[i] - suffix_min[i].

  6. If the score is less than or equal to k, return i.

  7. If no index satisfies the condition, return -1.

Why it works: By precomputing prefix maximums and suffix minimums, we ensure that the calculation of instability scores is exact and follows the definition in the problem. The algorithm preserves the original order and checks each index systematically, guaranteeing the smallest stable index is returned first.

Python Solution

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

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

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

        # Find the first stable index
        for i in range(n):
            if prefix_max[i] - suffix_min[i] <= k:
                return i
        return -1

The Python code first builds two helper arrays to store the running maximum from the left and the running minimum from the right. This allows checking each index in constant time. Iterating through the array and computing prefix_max[i] - suffix_min[i] ensures correctness according to the problem statement.

Go Solution

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

    // Compute prefix maximums
    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]
        }
    }

    // Compute suffix minimums
    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]
        }
    }

    // Find the first stable index
    for i := 0; i < n; i++ {
        if prefixMax[i]-suffixMin[i] <= k {
            return i
        }
    }
    return -1
}

In Go, we handle slices instead of arrays and manually check maximum and minimum conditions due to the lack of built-in max and min functions for integers. Otherwise, the approach mirrors the Python solution.

Worked Examples

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

i prefix_max[i] suffix_min[i] instability stable?
0 5 0 5 No
1 5 0 5 No
2 5 1 4 No
3 5 4 1 Yes

Return 3.

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

i prefix_max[i] suffix_min[i] instability stable?
0 3 1 2 No
1 3 1 2 No
2 3 1 2 No

Return -1.

Example 3: nums = [0], k = 0

i prefix_max[i] suffix_min[i] instability stable?
0 0 0 0 Yes

Return 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Two linear passes to build prefix_max and suffix_min, plus one linear pass to check instability
Space O(n) Two arrays of size n are used for prefix_max and suffix_min

The complexity is linear in both time and space, which is efficient and well within the problem constraints.

Test Cases

# Provided examples
assert Solution().firstStableIndex([5,0,1,4], 3) == 3  # standard case
assert Solution().firstStableIndex([3,2,1], 1) == -1   # no stable index
assert Solution().firstStableIndex([0], 0) == 0        # single element

# Additional cases
assert Solution().firstStableIndex([1,1,1,1], 0) == 0   # all equal elements
assert Solution().firstStableIndex([1,2,3,4,5], 4) == 0 # increasing sequence
assert Solution().firstStableIndex([5,4,3,2,1], 0) == 4 # decreasing sequence
assert Solution().firstStableIndex([2,2,3,1,4], 2) == 2 # random elements
assert Solution().firstStableIndex([1000000000], 0) == 0 # large single element
Test Why
[5,0,1,4], 3 Verifies example with first stable index not at 0
[3,2,1], 1 Verifies no index is stable
[0], 0 Tests minimal input
`[