Find the Smallest Balanced Index - Video Solutions
Find the Smallest Balanced Index | LeetCode 3862 | Prefix Sum vs. Suffix Product
Find the Smallest Balanced Index - Video Solution
Watch 8 video solutions for Find the Smallest Balanced Index, a medium level problem involving Array, Prefix Sum. This walkthrough by Sanyam IIT Guwahati has 905 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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:
- Left sum =
nums[0] = 2 - Right product =
nums[2] = 2 - Since the left sum equals the right product, index 1 is balanced.
No 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:
- Left sum =
2 + 8 = 10 - Right product =
2 * 5 = 10 - Since the left sum equals the right product, index 2 is balanced.
No smaller index satisfies the condition, so the answer is 2.
Example 3:
Input: nums = [1]
Output: -1
For indexi = 0:
- The left side is empty, so the left sum is 0.
- The right side is empty, so the right product is 1.
- Since the left sum does not equal the right product, index 0 is not balanced.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109
Approach Overview
Problem 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.
Complexity Analysis
| 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 |