Equilibrium Segment Balance — Problem Statement & Solution Guide

ArraysMediumPrefix Sum / Sliding Window

TimeO(n)

SpaceO(1)

Problem Description

Given an integer array nums, determine if there exists an index i such that the sum of elements to the left of i is equal to the sum of elements to the right of i. If such an index exists, return the leftmost index. If no such index exists, return -1. Note that the element at index i itself is excluded from both the left and right summations.

DSA Pattern Breakdown

"Equilibrium Segment Balance"

medium

WHY DOES IT MATTER?

Understanding prefix sums and running totals is essential because many interview problems ask you to compare sub‑array aggregates efficiently; mastering this pattern lets you turn nested loops into flat scans, dramatically improving scalability.

OPTIMIZATION CHALLENGE

The key insight is recognizing that the right‑hand sum can be expressed using the total sum and the already‑known left sum, eliminating the need for a second inner loop and collapsing the problem to a single linear traversal.

REAL-WORLD CONNECTION

In distributed log processing, services often need to compute the total traffic before and after a certain timestamp without re‑scanning the entire log; a running sum acts like a sliding window that provides instant left/right metrics, mirroring the equilibrium index logic.

During an interview, compute totalSum first, then iterate while updating leftSum; as soon as leftSum equals totalSum - leftSum - nums[i], return i. This one‑liner check shows you can think in terms of invariants rather than recomputation.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The equilibrium index problem is a classic illustration of the prefix‑sum technique, where we pre‑compute cumulative totals to answer range‑sum queries in constant time. A naive solution would recompute the left and right sums for each candidate index, leading to O(n²) time on large arrays—a performance killer for inputs with millions of elements. By first calculating the total sum of the array, we can derive the right‑hand sum on the fly: at each position, the right sum equals totalSum minus leftSum minus the current element, allowing a single linear pass that updates leftSum incrementally, achieving O(n) time and O(1) extra space. This paradigm—transforming a quadratic problem into a linear one via cumulative aggregates—is foundational in array‑based interview questions and underpins many real‑world streaming analytics where you need constant‑time windowed statistics.

Interview Questions on This Problem

Q1How would you modify the solution to return all equilibrium indices instead of just the leftmost one?

Maintain a list to collect indices whenever leftSum equals rightSum during the single pass; after the loop, return the list (or an empty list if none). The time and space complexities remain O(n) and O(k) respectively, where k is the number of equilibrium points.

Q2If the array contains 64‑bit integers that may overflow a 32‑bit sum, how do you safeguard your algorithm?

Use a 64‑bit integer type (e.g., long long in C++, long in Java, or Python's arbitrary‑precision int) for totalSum and leftSum to prevent overflow, ensuring that the arithmetic stays accurate even for very large values.

Q3Can you solve the problem in a single pass without first computing the total sum? Explain the trade‑offs.

Yes, by maintaining two running sums: leftSum (elements before i) and rightSum (elements after i) initialized by summing the entire array except the first element. As you iterate, you update rightSum by subtracting the current element before comparison. This still requires O(n) time and O(1) space, but computing the initial rightSum is effectively a pre‑pass, so the overall complexity remains linear.

Examples

Example 1

Input

[1, 7, 3, 6, 5, 6]

Output

Explanation: Step-by-step: with input [1, 7, 3, 6, 5, 6], we calculate the sum of elements to the left and right of each index. At index 3, the left sum is 1 + 7 + 3 = 11 and the right sum is 5 + 6 = 11, which are equal. Therefore, the leftmost index where the sums are equal is 3.

Example 2

Input

[1, 2, 3]

Output

-1

Explanation: Step-by-step: with input [1, 2, 3], we calculate the sum of elements to the left and right of each index. At index 0, the left sum is 0 and the right sum is 2 + 3 = 5, which are not equal. At index 1, the left sum is 1 and the right sum is 3, which are not equal. At index 2, the left sum is 1 + 2 = 3 and the right sum is 0, which are not equal. Therefore, there is no index where the sums are equal, and the output is -1.

Constraints

1 <= nums.length <= 10^5
-1000 <= nums[i] <= 1000
The sum of all elements in the array will not exceed 2^31 - 1

Optimal Approach & Strategy

First compute the total sum of the array. Then iterate once, maintaining a left sum; the right sum is derived as total - left - current element. Compare left and right at each step and return the first matching index.

Brute Force Approach

For each index, compute the sum of elements to its left and the sum of elements to its right by iterating over the sub‑arrays, then compare the two sums. This requires O(n²) time because each index triggers two linear scans.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function solution(nums) { 
       for (let i = 0; i < nums.length; i++) { 
           let leftSum = 0; 
           let rightSum = 0; 
           for (let j = 0; j < i; j++) { 
               leftSum += nums[j]; 
           } 
           for (let j = i + 1; j < nums.length; j++) { 
               rightSum += nums[j]; 
           } 
           if (leftSum === rightSum) { 
               return i; 
           } 
       } 
       return -1; 
   }

class Solution { 
   public: 
       int solution(vector<int>& nums) { 
           for (int i = 0; i < nums.size(); i++) { 
               int leftSum = 0; 
               int rightSum = 0; 
               for (int j = 0; j < i; j++) { 
                   leftSum += nums[j]; 
               } 
               for (int j = i + 1; j < nums.size(); j++) { 
                   rightSum += nums[j]; 
               } 
               if (leftSum == rightSum) { 
                   return i; 
               } 
           } 
           return -1; 
       } 
   };

class Solution { 
       public int solution(int[] nums) { 
           for (int i = 0; i < nums.length; i++) { 
               int leftSum = 0; 
               int rightSum = 0; 
               for (int j = 0; j < i; j++) { 
                   leftSum += nums[j]; 
               } 
               for (int j = i + 1; j < nums.length; j++) { 
                   rightSum += nums[j]; 
               } 
               if (leftSum == rightSum) { 
                   return i; 
               } 
           } 
           return -1; 
       } 
   }

def solution(nums): 
       for i in range(len(nums)): 
           left_sum = sum(nums[:i]) 
           right_sum = sum(nums[i+1:]) 
           if left_sum == right_sum: 
               return i 
       return -1

function solution(nums) { 
       for (let i = 0; i < nums.length; i++) { 
           let leftSum = 0; 
           let rightSum = 0; 
           for (let j = 0; j < i; j++) { 
               leftSum += nums[j]; 
           } 
           for (let j = i + 1; j < nums.length; j++) { 
               rightSum += nums[j]; 
           } 
           if (leftSum === rightSum) { 
               return i; 
           } 
       } 
       return -1; 
   }

Asked in Top Tech Interviews

Paytm

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Equilibrium Segment Balance Solution

Problem Statement

Input

Output

Input

Output

Constraints

More Arrays

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Equilibrium Segment Balance — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor