You are given an integer array nums.
An index i is balanced if the sum of elements strictly to the left of i equals the product of elements strictly to the right of i.
If there are no elements to the left, the sum is considered as 0. Similarly, if there are no elements to the right, the product is considered as 1.
Return an integer denoting the smallest balanced index. If no balanced index exists, return -1.
Example 1:
Input: nums = [2,1,2]
Output: 1
Explanation:
For index i = 1:
nums[0] = 2nums[2] = 2No smaller index satisfies the condition, so the answer is 1.
Example 2:
Input: nums = [2,8,2,2,5]
Output: 2
Explanation:
For index i = 2:
2 + 8 = 102 * 5 = 10No smaller index satisfies the condition, so the answer is 2.
Example 3:
Input: nums = [1]
Output: -1
For indexi = 0:
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109Problem Overview: You are given an integer array and must return the smallest index where the sum of elements to the left equals the sum of elements to the right. The element at the index itself is not included in either side. If multiple indices satisfy the condition, return the smallest one.
Approach 1: Brute Force Enumeration (O(n^2) time, O(1) space)
Check every index and compute the sum of the left part and the right part independently. For index i, iterate from 0 → i-1 to calculate the left sum, then from i+1 → n-1 for the right sum. If both sums match, return the index immediately since the scan proceeds left to right. This approach requires nested iteration and recomputes sums repeatedly, which leads to O(n^2) time complexity. It works for small inputs but becomes inefficient as the array grows.
Approach 2: Prefix Sum Enumeration (O(n) time, O(1) space)
The key observation is that repeatedly recalculating sums is unnecessary. First compute the total sum of the array. Then iterate once while maintaining a running leftSum. For each index i, the right side sum can be derived as totalSum - leftSum - nums[i]. If leftSum == rightSum, the current index is balanced and can be returned immediately because the traversal guarantees it is the smallest valid index.
This approach converts repeated summation into constant-time arithmetic using a running prefix value. The algorithm performs a single linear scan and stores only a few variables, resulting in O(n) time and O(1) extra space. It relies on the same principle used in many prefix sum problems and is commonly applied when comparing cumulative values on both sides of an index in an array.
Recommended for interviews: Start by explaining the brute force enumeration to show you understand the definition of a balanced index. Then optimize using a prefix sum style running total. Interviewers expect the O(n) scan because it eliminates redundant work and demonstrates familiarity with prefix-sum reasoning and constant‑space array traversal.
We first compute the total sum s of all elements in the array. Then we enumerate each index i from right to left, maintaining a variable p to record the product of all elements to the right of index i. When we reach index i, we first subtract nums[i] from s, then check whether s equals p; if so, we return index i. Next, we multiply p by nums[i]. If p is greater than or equal to s, the product will only keep growing and no balanced index can be found afterwards, so we can terminate the enumeration early.
If no balanced index is found after the enumeration, we return -1.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^2) | O(1) | Simple baseline approach or when input size is very small |
| Prefix Sum Enumeration | O(n) | O(1) | Preferred approach for interviews and large arrays |
Find the Smallest Balanced Index | LeetCode 3862 | Prefix Sum vs. Suffix Product • Sanyam IIT Guwahati • 770 views views
Watch 6 more video solutions →Practice Find the Smallest Balanced Index with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor