Python Program to Find Equilibrium Index of Array

You can find the equilibrium index of an array in Python by calculating the total sum and then iterating through the array while keeping track of the left sum; the index where left sum equals total sum minus left sum minus current element is the equilibrium index, as in for i in range(len(arr)): if left_sum == total_sum - left_sum - arr[i]: return i.

Examples

Input[1, 3, 5, 2, 2]

Output2

Input[2, 4, 6, 8, 10]

Output-1

Input[1]

Output0

How to Think About It

To find the equilibrium index, first find the total sum of all elements. Then move through the array, keeping track of the sum of elements to the left. At each position, check if the left sum equals the total sum minus the left sum and the current element. If yes, that position is the equilibrium index.

Algorithm

1

Calculate the total sum of the array elements.

2

Initialize left sum as 0.

3

Loop through each index in the array:

4

Check if left sum equals total sum minus left sum minus current element.

5

If yes, return the current index as equilibrium index.

6

If no index found, return -1.

Code

python

def find_equilibrium_index(arr):
    total_sum = sum(arr)
    left_sum = 0
    for i, num in enumerate(arr):
        if left_sum == total_sum - left_sum - num:
            return i
        left_sum += num
    return -1

# Example usage
arr = [1, 3, 5, 2, 2]
print(find_equilibrium_index(arr))

Output

2

Dry Run

Let's trace the array [1, 3, 5, 2, 2] through the code

1

Calculate total sum

total_sum = 1 + 3 + 5 + 2 + 2 = 13

2

Initialize left sum

left_sum = 0

3

Check index 0

left_sum = 0, total_sum - left_sum - arr[0] = 13 - 0 - 1 = 12, not equal

4

Update left sum

left_sum = 0 + 1 = 1

5

Check index 1

left_sum = 1, total_sum - left_sum - arr[1] = 13 - 1 - 3 = 9, not equal

6

Update left sum

left_sum = 1 + 3 = 4

7

Check index 2

left_sum = 4, total_sum - left_sum - arr[2] = 13 - 4 - 5 = 4, equal! Return 2

Index	Left Sum	Right Sum (total_sum - left_sum - arr[i])	Is Equilibrium?
0	0	12	No
1	1	9	No
2	4	4	Yes

Why This Works

Step 1: Calculate total sum

We find the sum of all elements to know the full array sum for comparison.

Step 2: Track left sum

We keep adding elements from the left to track the sum before the current index.

Step 3: Compare left and right sums

At each index, we check if left sum equals the right sum (total sum minus left sum and current element). If yes, that index balances the array.

Alternative Approaches

Using prefix sums array

python

def find_equilibrium_index_prefix(arr):
    prefix_sum = [0] * len(arr)
    prefix_sum[0] = arr[0]
    for i in range(1, len(arr)):
        prefix_sum[i] = prefix_sum[i-1] + arr[i]
    total_sum = prefix_sum[-1]
    for i in range(len(arr)):
        left = prefix_sum[i-1] if i > 0 else 0
        right = total_sum - prefix_sum[i]
        if left == right:
            return i
    return -1

print(find_equilibrium_index_prefix([1,3,5,2,2]))

This method uses extra space for prefix sums but makes sum calculations faster for multiple queries.

Brute force checking sums

python

def find_equilibrium_index_brute(arr):
    for i in range(len(arr)):
        if sum(arr[:i]) == sum(arr[i+1:]):
            return i
    return -1

print(find_equilibrium_index_brute([1,3,5,2,2]))

Simple but inefficient because it recalculates sums repeatedly, leading to slower performance on large arrays.

Complexity: O(n) time, O(1) space

Time Complexity

The program loops through the array once, so it runs in linear time O(n).

Space Complexity

Only a few variables are used, so space complexity is constant O(1).

Which Approach is Fastest?

The main approach is fastest for single queries due to O(n) time and O(1) space, while prefix sums use extra space but can be faster for multiple queries.

Approach	Time	Space	Best For
Single pass with left sum	O(n)	O(1)	Single query, minimal memory
Prefix sums array	O(n)	O(n)	Multiple queries, faster repeated sums
Brute force sums	O(n^2)	O(1)	Very small arrays or learning purposes