Skip to main content
Talentd

Find the Smallest Balanced Index - Solution & Explanation

MediumArrayPrefix Sum8 min readAsked at: Meta, Google
Practice this problem

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 index i = 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.
Therefore, no balanced index exists and the answer is -1.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= 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.

Solution

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n^2)O(1)Simple baseline approach or when input size is very small
Prefix Sum EnumerationO(n)O(1)Preferred approach for interviews and large arrays

Video Solution

Find the Smallest Balanced Index | LeetCode 3862 | Prefix Sum vs. Suffix Product • Sanyam IIT Guwahati • 905 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Find the Smallest Balanced Index easy or hard?
The problem is typically classified as Medium because the key insight is recognizing that right sums can be derived from the total sum and running prefix. Once that observation is made, the implementation becomes a straightforward linear scan.
Find the Smallest Balanced Index Python/Java solution
Most implementations follow the same pattern: compute the total array sum, iterate once, maintain a running left sum, and compare it with the derived right sum. This logic translates directly to Python, Java, C++, Go, and TypeScript with identical O(n) time complexity.
How to solve Find the Smallest Balanced Index in O(n)?
First compute the total sum of the array. Iterate through the array while tracking a running left sum. For each index i, compute rightSum = totalSum - leftSum - nums[i]. If leftSum equals rightSum, return i immediately because the traversal ensures it is the smallest valid index.
What is the best approach for Find the Smallest Balanced Index?
The optimal solution uses a prefix-sum style linear scan. Compute the total sum of the array, then iterate while maintaining a running left sum. The right sum at index i can be derived as totalSum - leftSum - nums[i]. This approach finds the smallest balanced index in O(n) time and O(1) space.
Is Find the Smallest Balanced Index asked at Google/Amazon/Meta?
Balanced index or pivot index style problems frequently appear in interviews at large tech companies. Variants that compare left and right cumulative sums are common at companies like Amazon and Google because they test array traversal and prefix-sum reasoning.
What data structure is used in Find the Smallest Balanced Index?
The problem mainly uses arrays with a prefix sum technique. Instead of storing a full prefix array, most optimal solutions maintain a running cumulative sum while iterating through the array.
What is the time complexity of Find the Smallest Balanced Index?
The optimal prefix-sum enumeration runs in O(n) time because the array is scanned once. Space complexity is O(1) since only a few variables store running totals. A naive brute-force approach would take O(n^2) time by recalculating sums for every index.

Ready to solve this problem?

Practice Find the Smallest Balanced Index with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays