Smallest Stable Index I 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
Smallest stable index I (Leetcode 3903) | Leetcode weekly contest 498.Prince Gupta Study · 10:42 · 94 views
LeetCode Weekly Contest 498 | Smallest Stable Index I & II | Easy → OptimizedProof2Code · 9:37 · 68 views
Leetcode Weekly Contest 498 Q1. Smallest Stable Index I #python #dsaADevOpsEngineer · 5:41 · 60 views
Leetcode Weekly Contest 498 | Smallest Stable Index I || Smallest Stable Index II | Q1 & Q2Pragya Gupta · 22:10 · 54 views
3903.Smallest Stable Index I | Weekly Contest 498 | Leetcode Daily |#leetcode #coding #telugu#pythoncodewarriortelugu · 2:28 · 48 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 3903 | Smallest Stable Index I | Weekly Contest 498 | O(N²) ApproachAsmita Mhetre · 9:40 · 44 views
Leetcode 3903 & 3904 | Smallest Stable Index I & II | Weekly Contest 498 | C++ | Easy | HindiPushkar Sehrawat · 32:24 · 42 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 <= 1000 <= nums[i] <= 1090 <= 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.
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 Recalculation | O(n^2) | O(1) | Useful for understanding the definition of the stable index or when constraints are very small |
| Prefix Sum Array | O(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 |
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.