Equilibrium Peak Finder — Problem Statement & Solution Guide
Problem Description
Given an array of integers, identify the smallest index i such that the sum of all elements strictly to the left of i equals the sum of all elements strictly to the right of i. The array is zero‑based indexed. If no such index exists, return -1.
Input format: The first line contains an integer n, the length of the array. The second line contains n space‑separated integers representing the array.
Output format: Output a single integer – the required index or -1 if none exists.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Equilibrium Peak Finder"
WHY DOES IT MATTER?
The pattern teaches how to convert repeated aggregate calculations into constant‑time updates, a skill vital for performance‑critical code where recomputation is prohibitive.
OPTIMIZATION CHALLENGE
The breakthrough is realizing that the right‑hand sum can be expressed as total‑left‑sum‑arr[i], eliminating the need for a nested loop and reducing the problem to a single pass with a running total.
REAL-WORLD CONNECTION
Think of a load balancer distributing requests across servers; the equilibrium index mirrors the point where the cumulative load on the left equals the load on the right, helping to decide where to split traffic for optimal latency.
During an interview, compute the total sum first, then walk the array once while updating a leftSum variable; remember to check the condition before you add the current element to leftSum.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The equilibrium index problem is a classic example of prefix‑sum reasoning. By pre‑computing the total sum of the array, we can derive the left‑hand sum at any index i as the cumulative sum of elements before i, and the right‑hand sum as total‑sum‑left‑sum‑arr[i]. A naive double‑loop would recompute these sums for each i, leading to O(n²) time, which quickly becomes infeasible for large n (e.g., n > 10⁵) due to both time constraints and cache inefficiency. The optimal paradigm leverages a single linear scan while maintaining a running left sum, updating the right sum implicitly by subtracting the current element from the total, thus achieving O(n) time and O(1) extra space.
This approach exemplifies the broader algorithmic pattern of "running totals" or "prefix sums" that turn a seemingly quadratic problem into linear time. It also demonstrates the importance of careful variable updates: the left sum must be updated after checking the equilibrium condition, while the right sum is derived on‑the‑fly. The insight that the total sum can be computed once and reused eliminates redundant work, which is the key to scaling the solution.
In practice, this technique extends to many array‑based challenges such as subarray sum queries, balance point detection in load‑balancing systems, and even financial ledger reconciliations where cumulative balances must match at a pivot point. Understanding why the naive method fails and how the prefix‑sum transformation resolves it is essential for any engineer tackling large‑scale data processing.
Interview Questions on This Problem
Q1How would you modify the solution to return all equilibrium indices instead of the smallest one?
Compute the total sum once, then iterate with a running left sum; whenever left sum equals total‑left‑sum‑arr[i], record i. Continue the scan to collect all matches, resulting in O(n) time and O(k) space where k is the number of equilibrium points.
Q2Can the equilibrium index be found in a streaming context where the array is too large to fit in memory?
Yes, by maintaining two passes: first stream to compute the total sum, then a second pass to maintain a running left sum and check the condition on the fly, requiring only O(1) additional memory and O(n) time across the two passes.
Q3What changes are needed if the array can contain negative numbers and we need the index where the absolute difference between left and right sums is minimized?
Track the absolute difference |left‑sum − (right‑sum)| at each index while scanning; keep the index with the smallest difference. This still runs in O(n) time and O(1) space, but the equality check becomes a minimization problem.
Examples
Input
5 1 2 3 4 6
Output
3
Explanation: Left sums: i=0 →0, i=1 →1, i=2 →3, i=3 →6, i=4 →10. Right sums: i=0 →15, i=1 →13, i=2 →10, i=3 →6, i=4 →0. Only i=3 satisfies left==right (6==6).
Input
4 1 2 3 3
Output
2
Explanation: Left sums: i=0 →0, i=1 →1, i=2 →3, i=3 →6. Right sums: i=0 →8, i=1 →6, i=2 →3, i=3 →0. i=2 gives left=3 and right=3, so index 2 is returned.
Input
3 1 2 3
Output
-1
Explanation: Left sums: 0,1,3. Right sums: 5,3,0. No index has equal left and right sums, hence -1.
Input
4 0 0 0 0
Output
0
Explanation: Left sum at i=0 is 0 and right sum is 0+0+0=0, so the first index 0 satisfies the condition.
Input
5 5 -5 5 -5 5
Output
0
Explanation: Left sum at i=0 is 0 and right sum is -5+5-5+5=0, so index 0 is the smallest equilibrium peak.
Constraints
- 1 <= n <= 100000
- -1000000000 <= nums[i] <= 1000000000
- The total sum of the array fits within a 64‑bit signed integer
Optimal Approach & Strategy
First compute the total sum of the array. Then traverse once, keeping a running left sum; the right sum is derived as total‑leftSum‑arr[i]. Compare left and right sums at each step to find the equilibrium index. This yields O(n) time and O(1) extra space.
Brute Force Approach
For each index, compute the sum of elements to its left and the sum of elements to its right using separate loops, then compare the two sums. This requires O(n²) time because each index recomputes sums from scratch.
Verified Code Solutions
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let idx = 0;
const n = input[idx++];
const arr = input.slice(idx, idx + n);
let total = arr.reduce((a, b) => a + b, 0);
let leftSum = 0;
let answer = -1;
for (let i = 0; i < n; i++) {
const rightSum = total - leftSum - arr[i];
if (leftSum === rightSum) {
answer = i;
break;
}
leftSum += arr[i];
}
console.log(answer);#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
vector<long long> arr(n);
for (int i = 0; i < n; ++i) cin >> arr[i];
long long total = 0;
for (long long val : arr) total += val;
long long leftSum = 0;
for (int i = 0; i < n; ++i) {
long long rightSum = total - leftSum - arr[i];
if (leftSum == rightSum) {
cout << i;
return 0;
}
leftSum += arr[i];
}
cout << -1;
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int[] arr = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
long total = 0;
for (int val : arr) total += val;
long leftSum = 0;
int answer = -1;
for (int i = 0; i < n; i++) {
long rightSum = total - leftSum - arr[i];
if (leftSum == rightSum) {
answer = i;
break;
}
leftSum += arr[i];
}
System.out.println(answer);
}
}
import sys
def find_equilibrium(arr):
total = sum(arr)
left_sum = 0
for i, val in enumerate(arr):
right_sum = total - left_sum - val
if left_sum == right_sum:
return i
left_sum += val
return -1
def main():
data = sys.stdin.read().strip().split()
if not data:
return
n = int(data[0])
arr = list(map(int, data[1:1+n]))
print(find_equilibrium(arr))
if __name__ == "__main__":
main()
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let idx = 0;
const n = input[idx++];
const arr = input.slice(idx, idx + n);
let total = arr.reduce((a, b) => a + b, 0);
let leftSum = 0;
let answer = -1;
for (let i = 0; i < n; i++) {
const rightSum = total - leftSum - arr[i];
if (leftSum === rightSum) {
answer = i;
break;
}
leftSum += arr[i];
}
console.log(answer);
Asked in Top Tech Interviews
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.