Equilibrium Index

Last Updated : 15 Jan, 2025

Given an array arr[] of size n, the task is to return an equilibrium index (if any) or -1 if no equilibrium index exists. The equilibrium index of an array is an index such that the sum of all elements at lower indexes equals the sum of all elements at higher indexes.

Note: When the index is at the start of the array, the left sum is 0, and when it's at the end, the right sum is 0.

Examples:

Input: arr[] = [1, 2, 0, 3]
Output: 2
Explanation: The sum of left of index 2 is 1 + 2 = 3 and sum on right of index 2 is 3.
Input: arr[] = [1, 1, 1, 1]
Output: -1
Explanation: There is no equilibrium index in the array.
Input: arr[] = [-7, 1, 5, 2, -4, 3, 0]
Output: 3
Explanation: The sum of left of index 3 is -7 + 1 + 5 = -1 and sum on right of index 3 is -4 + 3 + 0 = -1.

Table of Content

[Naive Approach] Using Nested Loop - O(n^2) Time and O(1) Space

The most basic idea is to use nested loops.

The outer loop iterates through all the indices one by one. Consider it as equilibrium index.
The inner loop finds out whether index i is equilibrium index or not, by checking if left side sum = right side sum.

C++

// C++ program to find equilibrium index of an array // using nested loop #include <iostream> #include <vector> using namespace std; int findEquilibrium(vector<int>& arr) {  // Check for indexes one by one until  // an equilibrium index is found   for (int i = 0; i < arr.size(); ++i) {    // Get left sum   int leftSum = 0;  for (int j = 0; j < i; j++)  leftSum += arr[j];  // Get right sum   int rightSum = 0;  for (int j = i + 1; j < arr.size(); j++)  rightSum += arr[j];  // If leftsum and rightsum are same, then   // index i is an equilibrium index  if (leftSum == rightSum)  return i;  }    // If equilibrium index doesn't exist  return -1; } int main() {  vector<int> arr = {-7, 1, 5, 2, -4, 3, 0};  cout << findEquilibrium(arr);  return 0; }

// C program to find equilibrium index of an array // using nested loop #include <stdio.h> int findEquilibrium(int arr[], int n) {    // Check for indexes one by one until  // an equilibrium index is found   for (int i = 0; i < n; ++i) {    // Get left sum  int leftSum = 0;  for (int j = 0; j < i; j++)  leftSum += arr[j];  // Get right sum  int rightSum = 0;  for (int j = i + 1; j < n; j++)  rightSum += arr[j];  // If leftsum and rightsum are same, then   // index i is an equilibrium index  if (leftSum == rightSum)  return i;  }  // If equilibrium index doesn't exist  return -1; } int main() {  int arr[] = {-7, 1, 5, 2, -4, 3, 0};  int n = sizeof(arr) / sizeof(arr[0]);  printf("%d", findEquilibrium(arr, n));  return 0; }

Java

// Java program to find equilibrium index of an array // using nested loop import java.util.*; class GfG {  static int findEquilibrium(int[] arr) {    // Check for indexes one by one until  // an equilibrium index is found   for (int i = 0; i < arr.length; ++i) {  // Get left sum  int leftSum = 0;  for (int j = 0; j < i; j++)  leftSum += arr[j];  // Get right sum  int rightSum = 0;  for (int j = i + 1; j < arr.length; j++)  rightSum += arr[j];  // If leftsum and rightsum are same, then   // index i is an equilibrium index  if (leftSum == rightSum)  return i;  }  // If equilibrium index doesn't exist  return -1;  }  public static void main(String[] args) {  int[] arr = {-7, 1, 5, 2, -4, 3, 0};  System.out.println(findEquilibrium(arr));  } }

Python

# Python program to find equilibrium index of an array # using nested loop def findEquilibrium(arr): # Check for indexes one by one until # an equilibrium index is found  for i in range(len(arr)): # Get left sum leftSum = sum(arr[:i]) # Get right sum rightSum = sum(arr[i + 1:]) # If leftsum and rightsum are same, then  # index i is an equilibrium index if leftSum == rightSum: return i # If equilibrium index doesn't exist return -1 if __name__ == '__main__': arr = [-7, 1, 5, 2, -4, 3, 0] print(findEquilibrium(arr))

// C# program to find equilibrium index of an array // using nested loop using System; using System.Collections.Generic; class GfG {  static int findEquilibrium(int[] arr) {    // Check for indexes one by one until  // an equilibrium index is found   for (int i = 0; i < arr.Length; ++i) {    // Get left sum  int leftSum = 0;  for (int j = 0; j < i; j++)  leftSum += arr[j];  // Get right sum  int rightSum = 0;  for (int j = i + 1; j < arr.Length; j++)  rightSum += arr[j];  // If leftsum and rightsum are same, then   // index i is an equilibrium index  if (leftSum == rightSum)  return i;  }  // If equilibrium index doesn't exist  return -1;  }  static void Main() {  int[] arr = {-7, 1, 5, 2, -4, 3, 0};  Console.WriteLine(findEquilibrium(arr));  } }

JavaScript

// JavaScript program to find equilibrium index of an array // using nested loop function findEquilibrium(arr) {  // Check for indexes one by one until  // an equilibrium index is found   for (let i = 0; i < arr.length; ++i) {  // Get left sum  let leftSum = 0;  for (let j = 0; j < i; j++)  leftSum += arr[j];  // Get right sum  let rightSum = 0;  for (let j = i + 1; j < arr.length; j++)  rightSum += arr[j];  // If leftsum and rightsum are same, then   // index i is an equilibrium index  if (leftSum === rightSum)  return i;  }  // If equilibrium index doesn't exist  return -1; } // Driver code let arr = [-7, 1, 5, 2, -4, 3, 0]; console.log(findEquilibrium(arr));

Output

[Better Approach] Prefix Sum and Suffix Sum Array - O(n) Time and O(n) Space

The idea is to remove the need of inner loop. Instead of calculating the left side sum and right side sum each time, precompute the prefix sum array and suffix sum array, and simply access this in O(1) time.
So for each index i, we can check if prefixSum[i - 1] = suffixSum[i + 1] but to avoid unnecessary boundary checks we can also check if prefixSum[i] = suffixSum[i].

C++

// C++ program to find equilibrium index of an array // using prefix sum and suffix sum arrays #include <iostream> #include <vector> using namespace std; int findEquilibrium(vector<int>& arr) {  int n = arr.size();    vector<int> pref(n, 0);  vector<int> suff(n, 0);  // Initialize the ends of prefix and suffix array  pref[0] = arr[0];  suff[n - 1] = arr[n - 1];  // Calculate prefix sum for all indices  for (int i = 1; i < n; i++)  pref[i] = pref[i - 1] + arr[i];  // Calculating suffix sum for all indices  for (int i = n - 2; i >= 0; i--)   suff[i] = suff[i + 1] + arr[i];  // Checking if prefix sum is equal to suffix sum  for (int i = 0; i < n; i++) {  if (pref[i] == suff[i])   return i;  }    // if equilibrium index doesn't exist  return -1; } int main() {  vector<int> arr = {-7, 1, 5, 2, -4, 3, 0};  cout << findEquilibrium(arr) << "\n";  return 0; }

// C program to find equilibrium index of an array // using prefix sum and suffix sum arrays #include <stdio.h> int findEquilibrium(int arr[], int n) {  int pref[n];  int suff[n];  // Initialize the ends of prefix and suffix array  pref[0] = arr[0];  suff[n - 1] = arr[n - 1];  // Calculate prefix sum for all indices  for (int i = 1; i < n; i++)   pref[i] = pref[i - 1] + arr[i];  // Calculating suffix sum for all indices  for (int i = n - 2; i >= 0; i--)   suff[i] = suff[i + 1] + arr[i];  // Checking if prefix sum is equal to suffix sum  for (int i = 0; i < n; i++) {  if (pref[i] == suff[i])  return i;  }  // if equilibrium index doesn't exist  return -1; } int main() {  int arr[] = {-7, 1, 5, 2, -4, 3, 0};  int n = sizeof(arr) / sizeof(arr[0]);  printf("%d\n", findEquilibrium(arr, n));  return 0; }

Java

// Java program to find equilibrium index of an array // using prefix sum and suffix sum arrays import java.util.*; class GfG {  static int findEquilibrium(int[] arr) {  int n = arr.length;  int[] pref = new int[n];  int[] suff = new int[n];  // Initialize the ends of prefix and suffix array  pref[0] = arr[0];  suff[n - 1] = arr[n - 1];  // Calculate prefix sum for all indices  for (int i = 1; i < n; i++)   pref[i] = pref[i - 1] + arr[i];  // Calculating suffix sum for all indices  for (int i = n - 2; i >= 0; i--)   suff[i] = suff[i + 1] + arr[i];  // Checking if prefix sum is equal to suffix sum  for (int i = 0; i < n; i++) {  if (pref[i] == suff[i])   return i;  }  // if equilibrium index doesn't exist  return -1;  }  public static void main(String[] args) {  int[] arr = {-7, 1, 5, 2, -4, 3, 0};  System.out.println(findEquilibrium(arr));  } }

Python

# Python program to find equilibrium index of an array # using prefix sum and suffix sum arrays def findEquilibrium(arr): n = len(arr) pref = [0] * n suff = [0] * n # Initialize the ends of prefix and suffix array pref[0] = arr[0] suff[n - 1] = arr[n - 1] # Calculate prefix sum for all indices for i in range(1, n): pref[i] = pref[i - 1] + arr[i] # Calculating suffix sum for all indices for i in range(n - 2, -1, -1): suff[i] = suff[i + 1] + arr[i] # Checking if prefix sum is equal to suffix sum for i in range(n): if pref[i] == suff[i]: return i # if equilibrium index doesn't exist return -1 if __name__ == "__main__": arr = [-7, 1, 5, 2, -4, 3, 0] print(findEquilibrium(arr))

// C# program to find equilibrium index of an array // using prefix sum and suffix sum arrays using System; class GfG {  static int findEquilibrium(int[] arr) {  int n = arr.Length;  int[] pref = new int[n];  int[] suff = new int[n];  // Initialize the ends of prefix and suffix array  pref[0] = arr[0];  suff[n - 1] = arr[n - 1];  // Calculate prefix sum for all indices  for (int i = 1; i < n; i++)   pref[i] = pref[i - 1] + arr[i];  // Calculating suffix sum for all indices  for (int i = n - 2; i >= 0; i--)   suff[i] = suff[i + 1] + arr[i];  // Checking if prefix sum is equal to suffix sum  for (int i = 0; i < n; i++) {  if (pref[i] == suff[i])   return i;  }  // if equilibrium index doesn't exist  return -1;  }  static void Main() {  int[] arr = {-7, 1, 5, 2, -4, 3, 0};  Console.WriteLine(findEquilibrium(arr));  } }

JavaScript

// JavaScript program to find equilibrium index of an array // using prefix sum and suffix sum arrays function findEquilibrium(arr) {  const n = arr.length;  const pref = new Array(n).fill(0);  const suff = new Array(n).fill(0);  // Initialize the ends of prefix and suffix array  pref[0] = arr[0];  suff[n - 1] = arr[n - 1];  // Calculate prefix sum for all indices  for (let i = 1; i < n; i++)   pref[i] = pref[i - 1] + arr[i];  // Calculating suffix sum for all indices  for (let i = n - 2; i >= 0; i--)   suff[i] = suff[i + 1] + arr[i];  // Checking if prefix sum is equal to suffix sum  for (let i = 0; i < n; i++) {  if (pref[i] === suff[i])   return i;  }  // if equilibrium index doesn't exist  return -1; } // Driver Code const arr = [-7, 1, 5, 2, -4, 3, 0]; console.log(findEquilibrium(arr));

Output

[Expected Approach] Running Prefix Sum and Suffix Sum - O(n) Time and O(1) Space

Now the above prefix sum array and suffix sum array approach can be further optimized in terms of space, by using prefix sum and suffix sum variables. The idea is that instead of storing the prefix sum and suffix sum for each element in an array, we can simply use the fact that
PrefixSum(arr[0 : pivot - 1]) + arr[pivot] + SuffixSum[pivot + 1: n - 1] = ArraySum
so, SuffixSum[pivot + 1: n - 1] = ArraySum - PrefixSum(arr[0 : pivot - 1])

Here, pivot refers to the index that we are currently checking for the equilibrium index.

C++

// C++ program to find equilibrium index of an array // using prefix sum and suffix sum variables #include <iostream> #include <vector> using namespace std; int equilibriumPoint(vector<int>& arr) {  int prefSum = 0, total = 0;  // Calculate the array sum  for (int ele: arr) {  total += ele;  }  // Iterate pivot over all the elements of the array and  // till left != right  for (int pivot = 0; pivot < arr.size(); pivot++) {  int suffSum = total - prefSum - arr[pivot];  if (prefSum == suffSum) {  return pivot;  }  prefSum += arr[pivot];  }  // there is no equilibrium point  return -1; } int main() {  vector<int> arr = { 1, 7, 3, 6, 5, 6 };  cout << equilibriumPoint(arr) << endl;  return 0; }

// C program to find equilibrium index of an array // using prefix sum and suffix sum variables #include <stdio.h> int equilibriumPoint(int arr[], int n) {  int prefSum = 0, total = 0;  // Calculate the array sum  for (int i = 0; i < n; i++) {  total += arr[i];  }  // Iterate pivot over all the elements of the array  for (int pivot = 0; pivot < n; pivot++) {  int suffSum = total - prefSum - arr[pivot];  if (prefSum == suffSum) {  return pivot;  }  prefSum += arr[pivot];  }  // There is no equilibrium point  return -1; } int main() {  int arr[] = {1, 7, 3, 6, 5, 6};  int n = sizeof(arr) / sizeof(arr[0]);  printf("%d\n", equilibriumPoint(arr, n));  return 0; }

Java

// Java program to find equilibrium index of an array // using prefix sum and suffix sum variables import java.util.*; class GfG {  static int equilibriumPoint(int[] arr) {  int prefSum = 0, total = 0;  // Calculate the array sum  for (int ele : arr) {  total += ele;  }  // Iterate pivot over all the elements of the array  for (int pivot = 0; pivot < arr.length; pivot++) {  int suffSum = total - prefSum - arr[pivot];  if (prefSum == suffSum) {  return pivot;  }  prefSum += arr[pivot];  }  // There is no equilibrium point  return -1;  }  public static void main(String[] args) {  int[] arr = {1, 7, 3, 6, 5, 6};  System.out.println(equilibriumPoint(arr));  } }

Python

# Python program to find equilibrium index of an array # using prefix sum and suffix sum variables def equilibriumPoint(arr): prefSum = 0 total = sum(arr) # Iterate pivot over all the elements of the array for pivot in range(len(arr)): suffSum = total - prefSum - arr[pivot] if prefSum == suffSum: return pivot prefSum += arr[pivot] # There is no equilibrium point return -1 if __name__ == "__main__": arr = [1, 7, 3, 6, 5, 6] result = equilibriumPoint(arr) print(result)

// C# program to find equilibrium index of an array // using prefix sum and suffix sum variables using System; class GfG {  static int equilibriumPoint(int[] arr) {  int prefSum = 0, total = 0;  // Calculate the array sum  foreach (int ele in arr) {  total += ele;  }  // Iterate pivot over all the elements of the array  for (int pivot = 0; pivot < arr.Length; pivot++) {  int suffSum = total - prefSum - arr[pivot];  if (prefSum == suffSum) {  return pivot;  }  prefSum += arr[pivot];  }  // There is no equilibrium point  return -1;  }  static void Main(string[] args) {  int[] arr = {1, 7, 3, 6, 5, 6};  Console.WriteLine(equilibriumPoint(arr));  } }

JavaScript

// JavaScript program to find equilibrium index of an array // using prefix sum and suffix sum variables function equilibriumPoint(arr) {  let prefSum = 0;  let total = arr.reduce((sum, ele) => sum + ele, 0);  // Iterate pivot over all the elements of the array  for (let pivot = 0; pivot < arr.length; pivot++) {  let suffSum = total - prefSum - arr[pivot];  if (prefSum === suffSum) {  return pivot;  }  prefSum += arr[pivot];  }  // There is no equilibrium point  return -1; } // Driver code const arr = [1, 7, 3, 6, 5, 6]; console.log(equilibriumPoint(arr));