Skip to main content
Talentd

Smallest Stable Index I - Solution & Explanation

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

Approach Overview

Problem Overview: You are given an integer array and need to return the smallest index where the sum of elements to the left of that index equals the sum of elements to the right. If multiple indices satisfy the condition, the smallest index is returned. If none exist, return -1.

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

Check every index and recompute the left and right sums from scratch. For index i, iterate from 0..i-1 to compute the left sum, then iterate from i+1..n-1 to compute the right sum. If the two sums match, return that index immediately because the problem asks for the smallest valid index. This approach is straightforward and requires no extra data structures, but repeated summation makes it quadratic. It works for small arrays but becomes slow when n grows.

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

Precompute cumulative sums so each range sum can be answered in constant time. Build a prefix 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 through the array once and compare both values for each index. This reduces the repeated summation cost and guarantees linear time. The technique is a common pattern when working with array range queries.

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

You do not actually need the full prefix array. First compute the total sum of the array. Then iterate from left to right while maintaining a running leftSum. For each index i, the right side is simply totalSum - leftSum - nums[i]. If leftSum == rightSum, return i. Otherwise update leftSum += nums[i] and continue. This approach performs a single pass and uses constant extra memory. It is the standard optimal pattern for balance-style index problems in prefix sum and array problems.

Recommended for interviews: The running prefix sum approach. Interviewers expect you to recognize that recomputing sums repeatedly is inefficient and that maintaining a running total avoids extra work. Mentioning the brute force approach first shows problem understanding, while deriving the O(n) solution demonstrates algorithmic optimization skills.

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 RecalculationO(n^2)O(1)Useful for understanding the definition of the stable index or when constraints are very small
Prefix Sum ArrayO(n)O(n)When many range-sum queries are needed or clarity is preferred over minimal memory
Running Prefix Sum (Optimal)O(n)O(1)Best general solution for interviews and large inputs

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 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.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays