Equilibrium Balancing Index — Problem Statement & Solution Guide

ArraysMediumPrefix Sum

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Arrays and solve the Equilibrium Balancing Index problem optimally.

TopicArrays

PatternPrefix Sum

TimeO(n)

SpaceO(1)

Problem Description

You are given an array of integers nums, find the leftmost index where the sum of all elements to the left is strictly equal to the sum of all elements to the right. If no such index exists, return -1.

DSA Pattern Breakdown

"Equilibrium Balancing Index"

medium

WHY DOES IT MATTER?

The equilibrium index pattern teaches candidates how to convert repeated sub‑array aggregations into constant‑time lookups using prefix sums—a cornerstone technique for array manipulation, range queries, and sliding‑window problems.

OPTIMIZATION CHALLENGE

The breakthrough is realizing that the right‑hand sum can be derived from the total sum minus the left sum and the current element, eliminating the need for a second traversal and collapsing the problem to O(n) time and O(1) extra space.

REAL-WORLD CONNECTION

Think of a load‑balancer distributing traffic across servers; the equilibrium index is the point where the cumulative load on the left cluster exactly matches the load on the right cluster, enabling optimal split decisions without recomputing totals each time.

During the interview, compute the total sum first, then iterate once while updating leftSum; remember to subtract the current element from the total before the equality check—this subtle ordering avoids off‑by‑one errors.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The equilibrium index problem is a classic example of prefix‑sum reasoning. A naive scan that recomputes the left and right sums for every candidate index incurs O(n²) time because each sum requires traversing a sub‑array, which quickly becomes prohibitive for large inputs (n can be up to 10⁵ or more in interview settings). The optimal paradigm leverages a single pass while maintaining a running total of the elements seen so far (the left sum) and the total sum of the entire array (the right sum). By subtracting the current element from the right sum before the comparison, we obtain the exact sum of elements to the right of the index without any extra traversal. This transforms the problem into a linear‑time solution that uses constant auxiliary space, satisfying both time‑critical and memory‑constrained constraints common in production systems.

Mathematically, let total = Σ nums[i] for i in [0, n‑1]. For each index i, leftSum = Σ nums[j] for j < i, and rightSum = total – leftSum – nums[i]. The index i is an equilibrium if leftSum == rightSum. Updating leftSum incrementally (leftSum += nums[i]) and adjusting total (rightSum = total – leftSum – nums[i]) yields O(1) per iteration. This approach also gracefully handles negative numbers and zeroes, which can trip up implementations that assume non‑negative inputs. The elegance of the prefix‑sum technique lies in its ability to collapse a seemingly quadratic problem into a linear scan, a pattern that recurs in many array‑based interview questions.

Interview Questions on This Problem

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

Maintain the same single‑pass logic but collect every index where leftSum == rightSum into a list. Since the scan is still O(n) and uses O(k) extra space for k equilibrium points, the overall complexity remains linear.

Q2A fintech platform stores daily transaction amounts in a circular buffer. How can you find an equilibrium point that respects the circular nature of the data?

Treat the circular buffer as two concatenated copies of the array and apply a sliding‑window prefix‑sum technique. Compute the total sum once, then slide a window of size n while updating left and right sums in O(1) per shift, yielding O(n) time and O(1) space.

Q3In a high‑growth startup, you need to support real‑time updates (insertions and deletions) to the array while still being able to query the equilibrium index efficiently. What data structure would you choose?

A Fenwick Tree (Binary Indexed Tree) or Segment Tree can maintain prefix sums with O(log n) updates and queries. To find an equilibrium index, perform a binary search on the prefix‑sum tree to locate the point where leftSum equals total‑leftSum‑value, achieving O(log n) per query after each update.

Examples

Example 1

Input

[1, 2, 3, 4, 5]

Output

Explanation: Step-by-step: with input [1, 2, 3, 4, 5], we calculate the sum of all elements to the left (1 + 2 + 3 = 6) and the sum of all elements to the right (4 + 5 = 9). Since 6 is not equal to 9, we move to the next index. At index 3, the sum of all elements to the left (1 + 2 + 3 = 6) is equal to the sum of all elements to the right (4). Therefore, the output is 3.

Example 2

Input

[10, 20, 30, 40, 50]

Output

Explanation: Step-by-step: with input [10, 20, 30, 40, 50], we calculate the sum of all elements to the left (10 + 20 + 30 = 60) and the sum of all elements to the right (40 + 50 = 90). Since 60 is not equal to 90, we move to the next index. At index 0, the sum of all elements to the left (10) is not equal to the sum of all elements to the right (40 + 50 = 90). Therefore, the output is 0.

Constraints

1 <= length of `nums` <= 10^5
-10^5 <= element in `nums` <= 10^5
At least one element in `nums` is non-zero

Optimal Approach & Strategy

Compute the total sum once, then iterate once while maintaining a left sum; derive the right sum as total‑leftSum‑currentElement, achieving O(n) time and O(1) space.

Brute Force Approach

For each index, recompute the sum of elements to its left and right by iterating over the sub‑arrays, leading to O(n²) time.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function equilibriumBalanceIndex(nums) {
      let leftSum = 0;
      let rightSum = nums.reduce((a, b) => a + b, 0);
      for (let i = 0; i < nums.length; i++) {
         rightSum -= nums[i];
         if (leftSum === rightSum) {
            return i;
         }
         leftSum += nums[i];
      }
      return -1;
   }

int equilibriumBalanceIndex(vector<int>& nums) {
      int leftSum = 0;
      int rightSum = 0;
      for (int num : nums) {
         rightSum += num;
      }
      for (int i = 0; i < nums.size(); i++) {
         rightSum -= nums[i];
         if (leftSum == rightSum) {
            return i;
         }
         leftSum += nums[i];
      }
      return -1;
   }

public int equilibriumBalanceIndex(int[] nums) {
      int leftSum = 0;
      int rightSum = 0;
      for (int num : nums) {
         rightSum += num;
      }
      for (int i = 0; i < nums.length; i++) {
         rightSum -= nums[i];
         if (leftSum == rightSum) {
            return i;
         }
         leftSum += nums[i];
      }
      return -1;
   }

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

function equilibriumBalanceIndex(nums) {
      let leftSum = 0;
      let rightSum = nums.reduce((a, b) => a + b, 0);
      for (let i = 0; i < nums.length; i++) {
         rightSum -= nums[i];
         if (leftSum === rightSum) {
            return i;
         }
         leftSum += nums[i];
      }
      return -1;
   }

Asked in Top Tech Interviews

PhonePe

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.