.png)
Equilibrium Index of an Array
Problem Statement
Given an array of integers, find the equilibrium index of the array.
An index i is called an equilibrium index if the sum of elements on the left of index i is equal to the sum of elements on the right of index i.
- The element at index i is not included in either sum.
- If multiple equilibrium indices exist, you may return any one (or all, depending on the problem).
- If no such index exists, return -1.
Example 1
Input
arr = [-7, 1, 5, 2, -4, 3, 0]
Output
3
Explanation
Index = 3
Left Sum = -7 + 1 + 5 = -1
Right Sum = -4 + 3 + 0 = -1
Example 2
Input
arr = [1, 2, 3]
Output
-1
Why This Problem Is Important
- Frequently asked interview question
- Tests understanding of:
- Prefix sums
- Left and right traversal
- Used in:
- Load balancing problems
- Financial calculations
- Array partitioning logic
Approaches Overview
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force | O(n²) | O(1) |
| Prefix Sum (Optimized) | O(n) | O(1) |
Approach 1: Brute Force Method
Idea
For every index:
- Compute sum of elements on the left
- Compute sum of elements on the right
- If both sums are equal, index is an equilibrium index
Algorithm
- Loop through each index i
- Calculate leftSum from 0 to i-1
- Calculate rightSum from i+1 to n-1
- If leftSum == rightSum, return i
- If none found, return -1
Time and Space Complexity
- Time Complexity: O(n²)
- Space Complexity: O(1)
C Implementation
#include<stdio.h>
int main() {
int arr[] = {-7, 1, 5, 2, -4, 3, 0};
int n = 7;
for(int i = 0; i < n; i++) {
int leftSum = 0, rightSum = 0;
for(int j = 0; j < i; j++)
leftSum += arr[j];
for(int j = i + 1; j < n; j++)
rightSum += arr[j];
if(leftSum == rightSum) {
printf("Equilibrium Index: %d", i);
return 0;
}
}
printf("Equilibrium Index: -1");
return 0;
}
Output
Equilibrium Index: 3
JavaScript Implementation
let arr = [-7, 1, 5, 2, -4, 3, 0];
let n = arr.length;
let found = false;
for (let i = 0; i < n; i++) {
let leftSum = 0, rightSum = 0;
for (let j = 0; j < i; j++)
leftSum += arr[j];
for (let j = i + 1; j < n; j++)
rightSum += arr[j];
if (leftSum === rightSum) {
console.log("Equilibrium Index:", i);
found = true;
break;
}
}
if (!found)
console.log("Equilibrium Index: -1");
Approach 2: Prefix Sum / Optimized Method
Idea
- First calculate the total sum of the array
- Traverse the array while maintaining leftSum
For each index:
rightSum = totalSum - leftSum - arr[i]- If leftSum == rightSum, equilibrium index found
Algorithm
- Compute totalSum of array
- Initialize leftSum = 0
- Traverse array from i = 0 to n-1
- For each index:
- rightSum = totalSum - leftSum - arr[i]
- If leftSum == rightSum, return i
- Update leftSum += arr[i]
- If none found, return -1
Time and Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(1)
C Implementation
#include<stdio.h>
int main() {
int arr[] = {-7, 1, 5, 2, -4, 3, 0};
int n = 7;
int totalSum = 0;
for(int i = 0; i < n; i++)
totalSum += arr[i];
int leftSum = 0;
for(int i = 0; i < n; i++) {
int rightSum = totalSum - leftSum - arr[i];
if(leftSum == rightSum) {
printf("Equilibrium Index: %d", i);
return 0;
}
leftSum += arr[i];
}
printf("Equilibrium Index: -1");
return 0;
}
C++ Implementation
#include<iostream>
using namespace std;
int main() {
int arr[] = {-7, 1, 5, 2, -4, 3, 0};
int n = 7;
int totalSum = 0;
for(int i = 0; i < n; i++)
totalSum += arr[i];
int leftSum = 0;
for(int i = 0; i < n; i++) {
int rightSum = totalSum - leftSum - arr[i];
if(leftSum == rightSum) {
cout << "Equilibrium Index: " << i;
return 0;
}
leftSum += arr[i];
}
cout << "Equilibrium Index: -1";
return 0;
}
Java Implementation
public class EquilibriumIndex {
public static void main(String[] args) {
int[] arr = {-7, 1, 5, 2, -4, 3, 0};
int totalSum = 0;
for(int num : arr)
totalSum += num;
int leftSum = 0;
for(int i = 0; i < arr.length; i++) {
int rightSum = totalSum - leftSum - arr[i];
if(leftSum == rightSum) {
System.out.println("Equilibrium Index: " + i);
return;
}
leftSum += arr[i];
}
System.out.println("Equilibrium Index: -1");
}
}
Python Implementation
arr = [-7, 1, 5, 2, -4, 3, 0]
total_sum = sum(arr)
left_sum = 0
for i in range(len(arr)):
right_sum = total_sum - left_sum - arr[i]
if left_sum == right_sum:
print("Equilibrium Index:", i)
break
left_sum += arr[i]
else:
print("Equilibrium Index: -1")
JavaScript Implementation
let arr = [-7, 1, 5, 2, -4, 3, 0];
let totalSum = arr.reduce((a, b) => a + b, 0);
let leftSum = 0;
for (let i = 0; i < arr.length; i++) {
let rightSum = totalSum - leftSum - arr[i];
if (leftSum === rightSum) {
console.log("Equilibrium Index:", i);
break;
}
leftSum += arr[i];
}
Dry Run (Optimized Approach)
Array: [-7, 1, 5, 2, -4, 3, 0]
Index | LeftSum | RightSum
0 | 0 | 7
1 | -7 | 6
2 | -6 | 1
3 | -1 | -1 → equilibrium index
Summary
- Equilibrium index balances left and right sums
- Brute force is intuitive but inefficient
- Prefix sum approach is optimal and interview-preferred
- Works with both positive and negative numbers
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
