The key insight is that we don't need to recompute sums from scratch at every index. Instead, we can track a running left sum and derive the right sum from what's left. This gives us a clean O(n) solution with O(1) extra space.

Clarifying the Problem

Before coding, let's nail down the edge cases:

What counts as "left" and "right"? The element at the pivot index itself is excluded from both sums. So for index i, left sum is arr[0..i-1] and right sum is arr[i+1..n-1].
What if multiple valid indices exist? Typically return the first one found (left to right).
What about edge indices? Index 0 has an empty left sum (0), and index n-1 has an empty right sum (0). Both are valid candidates.
Empty array? Return -1.

The Naive Approach (and Why We Can Do Better)

The brute force approach: for each index i, sum everything to the left and everything to the right, then compare. This is O(n) work per index, giving O(n²) overall. It works, but it's wasteful because we keep recomputing overlapping sums.

The Prefix Sum Insight

Here's the key observation. At any index i:

Left sum = sum of all elements before i
Right sum = total sum - left sum - arr[i]

If we precompute the total sum, then as we iterate left to right maintaining a running left_sum, we can compute the right sum in O(1) at each step. We just check if left_sum == total - left_sum - arr[i]. No extra array needed.

Let's trace through an example: [1, 7, 3, 6, 5, 6]

Total = 28
i=0: left=0, right=28-0-1=27. Not equal.
i=1: left=1, right=28-1-7=20. Not equal.
i=2: left=8, right=28-8-3=17. Not equal.
i=3: left=11, right=28-11-6=11. Equal! Return 3.

Implementation

def find_balanced_index(arr):
    if not arr:
        return -1

    total = sum(arr)
    left_sum = 0

    for i, val in enumerate(arr):
        # right_sum = total - left_sum - arr[i]
        if left_sum == total - left_sum - val:
            return i
        left_sum += val

    return -1

Notice that we update left_sum after the check, not before. This ensures left_sum at position i only reflects elements strictly to the left of i.

Complexity Analysis

Time: O(n). One pass to compute the total, one pass to find the pivot.
Space: O(1). Just two running integers, no auxiliary arrays.

Edge Cases Worth Testing

Single element: [5] returns 0. Left and right are both empty (sum = 0).
No valid index: [1, 2, 3] returns -1.
First or last index is valid: [0, 1, 2, -3], index 0 works since left sum is 0 and right sum is also 0.
All zeros: [0, 0, 0] returns 0 (the first valid index).
Negative numbers: The math holds regardless of sign, since we're using actual sums not absolute values.

Follow-up Thinking

A natural follow-up is: what if we want all balanced indices, not just the first? The structure barely changes. Instead of returning early, we collect every index where the condition holds, then return the list. Still O(n) time.

Another direction: what if the array is updated dynamically, and we need to repeatedly query for balanced indices? That pushes us toward a segment tree or Fenwick tree to handle prefix sums efficiently under mutation.

2072. Balanced Sum Index

Similar Questions