Equilibrium Point — Solution in Python, Java & C++
Equilibrium Point solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Equilibrium Point is an easy coding problem on arrays and prefix sum, asked in TCS and Capgemini interviews.
- Difficulty: Easy
- Topics: Arrays, Prefix Sum
- Asked at: TCS, Capgemini
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An index i is an equilibrium point if the sum of arr[0..i-1] equals the sum of arr[i+1..n-1]. The element at i itself belongs to neither side.
Return the smallest such index, or -1 if there is none. Indices are 0-based; an empty side sums to 0.
Example 1
Input: arr = [1,3,5,2,2]
Output: 2
Explanation: 1 + 3 = 4 on the left and 2 + 2 = 4 on the right.
Example 2
Input: arr = [1]
Output: 0
Explanation: Both sides are empty, so both sum to 0.
Example 3
Input: arr = [1,2,3]
Output: -1
Constraints
1 <= arr.length <= 100000-10000 <= arr[i] <= 10000
Hints for Equilibrium Point
Hint 1
Recomputing both sides at every index is O(n²). Compute the total once instead.
Hint 2
If
leftis the sum before indexi, the right side istotal - left - arr[i].Hint 3
Sweep left to right, testing the condition before adding
arr[i]toleft.
How to solve Equilibrium Point
Only two numbers matter at each index: the running prefix sum and the array total. The suffix sum follows from them by subtraction, so no second pass is needed.
Approach
- Add up the whole array into
total. - Sweep
ifrom0, keepingleft= sum ofarr[0..i-1](starting at0). - At each
i, the right side istotal - left - arr[i]; if it equalsleft, returni. - Otherwise add
arr[i]toleftand continue. Return-1if the sweep finishes.
Why it works
Returning on the first match gives the smallest index by construction, and the identity prefix + arr[i] + suffix = total makes the derived right-hand sum exact for every i, including the endpoints where one side is empty.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Adding
arr[i]toleftbefore the comparison shifts every test by one position. - A single-element array must answer
0, not-1— both empty sides are equal. - Negative values mean you cannot stop early when
leftexceeds half the total.
Reference solution
Python
from typing import List
def equilibriumPoint(arr: List[int]) -> int:
total = sum(arr)
left = 0
for i, x in enumerate(arr):
if left == total - left - x:
return i
left += x
return -1Java
public static int equilibriumPoint(int[] arr) {
long total = 0;
for (int x : arr) total += x;
long left = 0;
for (int i = 0; i < arr.length; i++) {
if (left == total - left - arr[i]) return i;
left += arr[i];
}
return -1;
}C++
int equilibriumPoint(vector<int>& arr) {
long long total = 0;
for (int x : arr) total += x;
long long left = 0;
for (int i = 0; i < (int) arr.size(); i++) {
if (left == total - left - arr[i]) return i;
left += arr[i];
}
return -1;
}JavaScript
var equilibriumPoint = function(arr) {
let total = 0;
for (let i = 0; i < arr.length; i++) total += arr[i];
let left = 0;
for (let i = 0; i < arr.length; i++) {
if (left === total - left - arr[i]) return i;
left += arr[i];
}
return -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Prefix Sum