Smallest Stable Index I

Difficulty: Easy | Acceptance: 68.20% | Paid: No Topics: Array, Prefix Sum

You are given a 0-indexed integer array nums.

An index i is called stable if nums[i] is equal to the sum of the first i elements of the array.

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

• Examples
• Constraints
• Brute Force
• Prefix Sum

Examples

Example 1:

Input: nums = [2,1,6,4]
Output: -1
Explanation:
- i = 0: sum of first 0 elements = 0, nums[0] = 2. 0 != 2.
- i = 1: sum of first 1 elements = 2, nums[1] = 1. 2 != 1.
- i = 2: sum of first 2 elements = 3, nums[2] = 6. 3 != 6.
- i = 3: sum of first 3 elements = 9, nums[3] = 4. 9 != 4.
No stable index exists.

Example 2:

Input: nums = [1,1,1,1]
Output: 1
Explanation:
- i = 0: sum of first 0 elements = 0, nums[0] = 1. 0 != 1.
- i = 1: sum of first 1 elements = 1, nums[1] = 1. 1 == 1.
Index 1 is the smallest stable index.

Example 3:

Input: nums = [0,0,0]
Output: 0
Explanation:
- i = 0: sum of first 0 elements = 0, nums[0] = 0. 0 == 0.
Index 0 is the smallest stable index.

Constraints

- 1 <= nums.length <= 100
- 0 <= nums[i] <= 10^9
- 0 <= k <= 10^9

Brute Force

Intuition We can directly implement the definition of a stable index. For every index i, we calculate the sum of elements from 0 to i-1 and check if it equals nums[i].

Steps

• Iterate through the array from index 0 to n-1.
• For each index i, initialize a current_sum to 0.
• Iterate from index 0 to i-1 and add each element to current_sum.
• If current_sum equals nums[i], return i.
• If the loop finishes without finding a stable index, return -1.

class Solution:
    def smallestStableIndex(self, nums: list[int]) -> int:
        n = len(nums)
        for i in range(n):
            prefix_sum = 0
            for j in range(i):
                prefix_sum += nums[j]
            if prefix_sum == nums[i]:
                return i
        return -1

Complexity

• Time: O(n²) - For each index, we sum up to i elements.
• Space: O(1) - We only use a few variables for summation.
• Notes: This approach is inefficient for large arrays (n up to 10⁵) and will likely result in a Time Limit Exceeded error.

Prefix Sum

Intuition Instead of recalculating the sum for every index from scratch, we can maintain a running total (prefix sum) as we iterate through the array. At index i, the running sum represents the sum of elements before i.

Steps

• Initialize prefix_sum to 0.
• Iterate through the array with index i from 0 to n-1.
• Check if prefix_sum is equal to nums[i]. If yes, return i.
• Add nums[i] to prefix_sum.
• If the loop completes, return -1.

class Solution:
    def smallestStableIndex(self, nums: list[int]) -> int:
        prefix_sum = 0
        for i, num in enumerate(nums):
            if prefix_sum == num:
                return i
            prefix_sum += num
        return -1

Complexity

• Time: O(n) - We traverse the array exactly once.
• Space: O(1) - We only store the running sum.
• Notes: This is the optimal solution. Note that we use long (Java) and long long (C++) to prevent integer overflow since the sum can exceed the 32-bit integer range.