When solving coding problems, one frequently encountered challenge is finding the equilibrium point in an array. This is a classical problem in algorithm design that tests the ability to balance sums efficiently without resorting to brute force. Let’s break it down in detail.
📌 Problem Statement
Given an array A of n non-negative integers, the task is to find the first equilibrium point. An equilibrium point is an index such that the sum of elements before it is equal to the sum of elements after it.
-
Use 1-based indexing.
-
If no equilibrium point exists, return
-1.
Constraints:
-
1 <= n <= 10^5 -
0 <= A[i] <= 10^9
🔎 Examples
Example 1
Input:
n = 5
A[] = {1, 3, 5, 2, 2}
Process:
-
Index 1 → Left sum = 0, Right sum = 12 ❌
-
Index 2 → Left sum = 1, Right sum = 9 ❌
-
Index 3 → Left sum = 4, Right sum = 4 ✅
Output:
3
Example 2
Input:
n = 1
A[] = {1}
Since there’s only one element, it automatically becomes the equilibrium point.
Output:
1
⚡ Why Brute Force Fails
A naïve approach would be:
-
For each index
i, compute sum of elements before and after it. -
Compare the two.
This requires O(n²) time in the worst case, which is inefficient for large inputs (n ≤ 100,000). Hence, we need a more optimized approach.
✅ Optimized Approaches
1. Total Sum & Left Sum Method (Efficient Approach)
We can achieve O(n) time and O(1) space using the following idea:
-
Compute the total sum of the array.
-
Traverse through the array while maintaining a left sum.
-
At each index
i, check:leftSum == totalSum - leftSum - A[i]If true, this is the equilibrium point.
-
Update
leftSum += A[i]and continue.
2. Prefix Sum Approach
Another approach uses prefix sums to quickly compute left and right sums:
-
Create an array
prefix[]whereprefix[i]stores the sum of elements from0toi. -
For each index
i, left sum =prefix[i-1], right sum =prefix[n-1] - prefix[i]. -
If left sum == right sum → equilibrium found.
Complexity:
-
Time Complexity:
O(n)(one pass to compute prefix, one pass to check). -
Space Complexity:
O(n)(extra array for prefix sums).
This approach is less space-efficient than the total sum method, but conceptually easier to understand.
🧑💻 Implementation (Java - Total Sum Method)
class Solution {
public static int equilibriumPoint(long arr[], int n) {
long totalSum = 0, leftSum = 0;
// Step 1: Find total sum
for (int i = 0; i < n; i++) {
totalSum += arr[i];
}
// Step 2: Traverse and check equilibrium condition
for (int i = 0; i < n; i++) {
totalSum -= arr[i]; // totalSum now acts as rightSum
if (leftSum == totalSum) {
return i + 1; // 1-based index
}
leftSum += arr[i];
}
return -1; // No equilibrium point found
}
}
🧑💻 Implementation (Python - Prefix Sum Method)
def equilibriumPoint(arr, n):
prefix = [0] * n
prefix[0] = arr[0]
# Build prefix sum array
for i in range(1, n):
prefix[i] = prefix[i-1] + arr[i]
total_sum = prefix[-1]
for i in range(n):
left_sum = prefix[i-1] if i > 0 else 0
right_sum = total_sum - prefix[i]
if left_sum == right_sum:
return i + 1 # 1-based index
return -1
🕒 Complexity Analysis
Total Sum Method
-
Time Complexity:
O(n) -
Space Complexity:
O(1)
Prefix Sum Method
-
Time Complexity:
O(n) -
Space Complexity:
O(n)
Both are efficient, but the Total Sum Method is preferred due to lower space usage.
🎯 Key Observations
-
The equilibrium point is essentially a balance point.
-
Total sum helps avoid recomputation of right sums.
-
Prefix sums provide an intuitive way to check but need extra space.
-
Works efficiently under given constraints.
📌 Applications
-
Load balancing: Splitting workloads evenly.
-
Financial analysis: Checking balance points in profit/loss arrays.
-
Partitioning problems: Finding equal subarray sums.
🚀 Conclusion
The equilibrium point problem highlights the power of prefix sums and optimized linear scanning. While prefix sums provide clarity, the total sum + left sum approach is the most space-efficient. By reducing unnecessary recalculations, we turn an O(n²) problem into an O(n) one, making it highly useful in interviews and real-world applications.
