Is Smallest Stable Index I easy or hard?

Smallest Stable Index I is considered an Easy problem. The main insight is recognizing that repeated summation can be avoided with a prefix-sum technique, reducing the complexity from O(n^2) to O(n).

Smallest Stable Index I Python/Java solution

Both Python and Java implementations follow the same idea: compute the total sum, iterate through the array, maintain a running left sum, and compare it with the computed right sum. The algorithm stays O(n) regardless of language.

How to solve Smallest Stable Index I in O(n)?

Calculate the total sum of the array first. Traverse the array while tracking the cumulative left sum. At each index compute the right sum using totalSum - leftSum - nums[i]. If both sides match, that index is the smallest stable index.

What is the best approach for Smallest Stable Index I?

The optimal approach uses a running prefix sum. First compute the total array sum, then iterate while maintaining a leftSum. For each index i, compute rightSum = totalSum - leftSum - nums[i]. When leftSum equals rightSum, return that index. This runs in O(n) time and O(1) extra space.

Is Smallest Stable Index I asked at Google/Amazon/Meta?

Balance index and prefix-sum style problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants include pivot index and equilibrium index problems that use the same prefix-sum technique.

What data structure is used in Smallest Stable Index I?

The problem primarily uses arrays with a prefix-sum technique. No advanced data structures are required. The optimal approach only keeps a few integer variables to track total and running sums.

What is the time complexity of Smallest Stable Index I?

The optimal solution runs in O(n) time because the array is scanned once after computing the total sum. Space complexity is O(1) when using a running prefix sum, or O(n) if a full prefix array is stored.

3903. Smallest Stable Index I - Practice Online

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

For each index i, define its instability score as max(nums[0..i]) - min(nums[i..n - 1]).

In other words:

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

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

Return the smallest stable index. If no such index exists, return -1.

Example 1:

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

Output: 3

Explanation:

At index 0: The maximum in [5] is 5, and the minimum in [5, 0, 1, 4] is 0, so the instability score is 5 - 0 = 5.
At index 1: The maximum in [5, 0] is 5, and the minimum in [0, 1, 4] is 0, so the instability score is 5 - 0 = 5.
At index 2: The maximum in [5, 0, 1] is 5, and the minimum in [1, 4] is 1, so the instability score is 5 - 1 = 4.
At index 3: The maximum in [5, 0, 1, 4] is 5, and the minimum in [4] is 4, so the instability score is 5 - 4 = 1.
This is the first index with an instability score less than or equal to k = 3. Thus, the answer is 3.

Example 2:

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

Output: -1

Explanation:

At index 0, the instability score is 3 - 1 = 2.
At index 1, the instability score is 3 - 1 = 2.
At index 2, the instability score is 3 - 1 = 2.
None of these values is less than or equal to k = 1, so the answer is -1.

Example 3:

Input: nums = [0], k = 0

Output: 0

Explanation:

At index 0, the instability score is 0 - 0 = 0, which is less than or equal to k = 0. Therefore, the answer is 0.

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 10⁹
0 <= k <= 10⁹