Skip to main content
Talentd

Smallest Stable Index II - Solution & Explanation

MediumArray9 min read
Practice this problem

Problem Statement

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 <= 105
  • 0 <= nums[i] <= 109
  • 0 <= k <= 109

Approach Overview

Problem Overview: Given an integer array, a stable index is an index where the sum of elements on the left equals the sum of elements on the right. The task is to return the smallest such index. If no index satisfies the condition, return -1.

Approach 1: Brute Force Scan (O(n^2) time, O(1) space)

Iterate through every index i and recompute the left and right sums each time. For each position, loop from 0..i-1 to compute the left sum and from i+1..n-1 to compute the right sum. If the two sums match, return the index immediately since the goal is the smallest valid index. This approach uses constant extra memory but performs repeated work, leading to quadratic time.

Approach 2: Prefix Sum Array (O(n) time, O(n) space)

Precompute a prefix sum array where prefix[i] stores the sum of elements from 0..i. The left sum for index i becomes prefix[i-1], and the right sum becomes prefix[n-1] - prefix[i]. Iterate once through the array and compare both sums. Each lookup becomes constant time, reducing overall complexity to linear time while using extra memory for the prefix array. This technique is common when solving problems involving cumulative ranges in arrays and prefix sums.

Approach 3: Running Prefix Sum (Optimal) (O(n) time, O(1) space)

First compute the total sum of the array. Then iterate through the array while maintaining a running leftSum. For index i, the right sum is simply totalSum - leftSum - nums[i]. Compare leftSum and the computed right sum. If they match, return i. After the check, add nums[i] to leftSum and continue. This eliminates the need for an auxiliary prefix array while preserving linear performance.

Recommended for interviews: The running prefix sum approach is the expected solution. Brute force shows the baseline reasoning, but interviewers usually want to see the observation that the right side can be derived from the total sum and a running left sum. That insight reduces repeated work and demonstrates strong understanding of array traversal and cumulative sum techniques.

Solution

First, we preprocess an array right, where right[i] represents the minimum value among the elements in nums from index i to index n - 1. We can compute the right array by traversing nums from back to front.

Next, we traverse the nums array from front to back, maintaining a variable left, which represents the maximum value among the elements in nums from index 0 to index i. For each index i, we calculate the instability score as left - right[i]. If the instability score is less than or equal to k, we return index i. If no such index is found after the traversal, we return -1.

The time complexity is O(n) and the space complexity is O(n), where n is the length of the nums array.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ScanO(n^2)O(1)Good for initial reasoning or very small arrays
Prefix Sum ArrayO(n)O(n)Useful when prefix sums are reused for multiple queries
Running Prefix Sum (Optimal)O(n)O(1)Best general solution with minimal memory usage

Video Solution

Smallest Stable Index I & II | LeetCode 3903 | LeetCode 3904 | Weekly Contest 498 | Developer Coder • Developer Coder • 165 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Smallest Stable Index II easy or hard?
Smallest Stable Index II is generally considered a medium-level problem. The core logic is straightforward once you recognize the prefix sum pattern, but identifying the constant-space optimization is the key insight.
Smallest Stable Index II Python/Java solution
Both Python and Java implementations follow the same idea: compute the total sum, track a running left sum, and check whether leftSum equals totalSum - leftSum - nums[i] at each index. This keeps the solution O(n) with constant extra space.
How to solve Smallest Stable Index II in O(n)?
First compute the total sum of the array. Traverse the array while keeping a running leftSum. At index i, compute rightSum = totalSum - leftSum - nums[i]. If leftSum equals rightSum, return i. Update leftSum by adding nums[i] and continue. This produces a linear-time solution.
What is the best approach for Smallest Stable Index II?
The optimal solution uses a running prefix sum. Compute the total sum of the array, then iterate while maintaining a left sum. For each index i, compute the right sum as totalSum - leftSum - nums[i]. If left and right sums match, return the index. This runs in O(n) time with O(1) extra space.
Is Smallest Stable Index II asked at Google/Amazon/Meta?
Problems based on pivot index and prefix sums frequently appear in interviews at companies like Amazon, Google, and Meta. Variations that require identifying balance points or equal partitions in arrays are common screening questions.
What data structure is used in Smallest Stable Index II?
The primary data structure is an array. The algorithm typically relies on prefix sum techniques or running cumulative sums to compare the left and right portions efficiently.
What is the time complexity of Smallest Stable Index II?
The optimal approach runs in O(n) time because the array is scanned once while maintaining running sums. Space complexity can be O(1) using the running prefix technique, or O(n) if a separate prefix sum array is stored.

Ready to solve this problem?

Practice Smallest Stable Index II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays