Finding Equilibrium Index of an Array in Python

Understanding Equilibrium Index

The equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes.

We will explore three different methods to solve this problem in Python.

Method 1: Using Brute Force

def find_equilibrium(arr):
    n = len(arr)
    for i in range(n):
        left_sum = sum(arr[:i])
        right_sum = sum(arr[i+1:])
        if left_sum == right_sum:
            print(f"Equilibrium Index: {i}")

arr = [-7, 1, 5, 2, -4, 3, 0]
find_equilibrium(arr)
            

Output:

Equilibrium Index: 3
Equilibrium Index: 6
            

Method 2: Using Prefix Sum

def find_equilibrium(arr):
    total_sum = sum(arr)
    left_sum = 0
    for i, num in enumerate(arr):
        total_sum -= num
        if left_sum == total_sum:
            print(f"Equilibrium Index: {i}")
        left_sum += num

arr = [-7, 1, 5, 2, -4, 3, 0]
find_equilibrium(arr)
            

Output:

Equilibrium Index: 3
Equilibrium Index: 6
            

Method 3: Using Recursion

def equilibrium_helper(arr, index, left_sum, total_sum):
    if index == len(arr):
        return -1
    total_sum -= arr[index]
    if left_sum == total_sum:
        return index
    return equilibrium_helper(arr, index + 1, left_sum + arr[index], total_sum)

def find_equilibrium(arr):
    total_sum = sum(arr)
    eq_index = equilibrium_helper(arr, 0, 0, total_sum)
    if eq_index != -1:
        print(f"Equilibrium Index: {eq_index}")

arr = [-7, 1, 5, 2, -4, 3, 0]
find_equilibrium(arr)
            

Output:

Equilibrium Index: 3