Smallest Stable Index II solution and explanation
9 more videos on this problem
Smallest Stable Index I & II | LeetCode 3903 | LeetCode 3904 | Weekly Contest 498 | Developer CoderDeveloper Coder · 9:56 · 165 views
LeetCode Weekly Contest 498 | Smallest Stable Index I & II | Easy → OptimizedProof2Code · 9:37 · 68 views
Smallest stable index II (Leetcode 3904) | Leetcode weekly contest 498.Prince Gupta Study · 21:49 · 64 views
Leetcode Weekly Contest 498 | Smallest Stable Index I || Smallest Stable Index II | Q1 & Q2Pragya Gupta · 22:10 · 54 views
3903.Smallest Stable Index II | Weekly Contest 498 | Leetcode Daily | #leetcode #telugu #dsa #pythoncodewarriortelugu · 5:48 · 50 views
LeetCode 3904 | Smallest Stable Index II | Weekly Contest 498 | O(N) Optimized SolutionAsmita Mhetre · 7:28 · 47 views
Smallest Stable Index I & II | Leetcode 3903 & 3904 | Explanation With Code | Javacodewithsitaram · 25:49 · 46 views
LeetCode Contest 498 Solutions | Smallest Stable Index I & II (Q1 + Q2 Explained) | LC 3903 & 3904Core Logic Dev · 19:11 · 44 views
Leetcode Weekly Contest 498 Q2. Smallest Stable Index II #python #dsaADevOpsEngineer · 5:21 · 26 views
3904. Smallest Stable Index II | LeetCode Weekly Contest 498 Simple SolutionBEASTCODES · 8:33 · 22 views
The problem
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 indexi.min(nums[i..n - 1])is the smallest value among the elements from indexito indexn - 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 is5 - 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 is5 - 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 is5 - 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 is5 - 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 <= 1050 <= nums[i] <= 1090 <= 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.
class Solution:
def firstStableIndex(self, nums: list[int], k: int) -> int:
n = len(nums)
right = [nums[-1]] * n
for i in range(n - 2, -1, -1):
right[i] = min(right[i + 1], nums[i])
left = 0
for i, x in enumerate(nums):
left = max(left, x)
if left - right[i] <= k:
return i
return -1class Solution {
public int firstStableIndex(int[] nums, int k) {
int n = nums.length;
int[] right = new int[n];
right[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) {
right[i] = Math.min(right[i + 1], nums[i]);
}
int left = 0;
for (int i = 0; i < n; i++) {
left = Math.max(left, nums[i]);
if (left - right[i] <= k) {
return i;
}
}
return -1;
}
}class Solution {
public:
int firstStableIndex(vector<int>& nums, int k) {
int n = nums.size();
vector<int> right(n);
right[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; --i) {
right[i] = min(right[i + 1], nums[i]);
}
int left = 0;
for (int i = 0; i < n; ++i) {
left = max(left, nums[i]);
if (left - right[i] <= k) {
return i;
}
}
return -1;
}
};function firstStableIndex(nums: number[], k: number): number {
const n = nums.length;
const right = new Array<number>(n);
right[n - 1] = nums[n - 1];
for (let i = n - 2; i >= 0; i--) {
right[i] = Math.min(right[i + 1], nums[i]);
}
let left = 0;
for (let i = 0; i < n; i++) {
left = Math.max(left, nums[i]);
if (left - right[i] <= k) {
return i;
}
}
return -1;
}func firstStableIndex(nums []int, k int) int {
n := len(nums)
right := make([]int, n)
right[n-1] = nums[n-1]
for i := n - 2; i >= 0; i-- {
right[i] = min(right[i+1], nums[i])
}
left := 0
for i, x := range nums {
left = max(left, x)
if left-right[i] <= k {
return i
}
}
return -1
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan | O(n^2) | O(1) | Good for initial reasoning or very small arrays |
| Prefix Sum Array | O(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 |
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.