September 5, 2025

🔹 Finding the First Equilibrium Point in an Array

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:

  1. Compute the total sum of the array.

  2. Traverse through the array while maintaining a left sum.

  3. At each index i, check:

    leftSum == totalSum - leftSum - A[i]

    If true, this is the equilibrium point.

  4. Update leftSum += A[i] and continue.

2. Prefix Sum Approach

Another approach uses prefix sums to quickly compute left and right sums:

  1. Create an array prefix[] where prefix[i] stores the sum of elements from 0 to i.

  2. For each index i, left sum = prefix[i-1], right sum = prefix[n-1] - prefix[i].

  3. 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

  1. The equilibrium point is essentially a balance point.

  2. Total sum helps avoid recomputation of right sums.

  3. Prefix sums provide an intuitive way to check but need extra space.

  4. 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.

By