What is equilibrium point short notes?

An equilibrium point is a state where opposing forces balance out, resulting in no net change.

Equilibrium index of an array

Introduction

The equilibrium point refers to a specific element in an array where the sum of elements on its left is equal to the sum of elements on its right. They are used in control systems to keep things steady and balanced. In short, it is a state where the output of the control system remains constant, even when the input values vary. In this blog, we will discuss an array of problem that has been asked frequently in Interviews.

The problem is to find the Equilibrium Point of an array.

We are given N elements in an array, and we need to find the index such that the sum of the elements towards its left is equal to the sum of the element towards its right.

The equilibrium index of an array is the index at which the sum of the components at lower and higher indices is equal. In other words, the index i at which the sum of the items at indices less than i equals the sum of the elements at indices greater than i is the equilibrium index of an array.

Example of Equilibrium Point

Example: 1,7,3,6,5,6

At index 0, we have 1.

Sum of all elements towards the left of 1 = 0.

Sum of all elements towards the right of 1 = 27.

At index 1, we have 7.

Sum of all elements towards the left of 7 = 1.

Sum of all elements towards the right of 1 = 20.

At index 2, we have 3.

Sum of all elements towards the left of 3 = 8.

Sum of all elements towards the right of 3 = 17.

At index 3, we have 6.

Sum of all elements towards the left of 6 = 11.

Sum of all elements towards the right of 6 = 11.

Here left sum equals the right sum.

∴Index 3 is returned as the desired answer.

Also see, Euclid GCD Algorithm

Naive Approach to Find Equilibrium Point

The naive approach to finding the Equilibrium Point of an array would be taking each element from the start of the array, finding its left and the right sum. If both are equal, return the taken element index or perform the same steps with the next element.

Time Complexity for finding left and right sum for one element chosen = n.

For n elements, it would take = n² time.

Start iterating from the first index element.

⬇

Find its left sum.

⬇

Find its right sum.

⬇

Check whether the left equals the right sum.

⬇

If equal, then return index.

⬇

If not equal, then move to the next element and perform all the above steps.

Optimised Approach to Find Equilibrium Point

To minimise the time complexity, we can do the above implementation in a more optimised way.

So in the most optimal approach, the time complexity for this problem will reduce from O (n²) to O (n).

Now we will be discussing our second, the optimised approach.

Find the total sum and store it in a variable.

⬇

Start traversing for all elements starting from the 0th index.

⬇

Calculate the sum of all elements towards the right.

It can be found by subtracting the left sum and number at the current index from the total sum.

⬇

If the left sum equals the right sum, return index and thus come out of the loop.

⬇

Keep track of the sum of all elements towards the left.

It can be found by adding all elements towards the left.

⬇

If no such position exists where left sum equals right sum, then return -1.

The algorithm finds the Equilibrium Point of an array by simultaneously keeping track of the left and right sum.

Till now, I assume you must have got the basic idea of what has been asked in the Equilibrium Index problem statement. So, I strongly recommend you first give it a try.

Please have a look at the algorithm, and then again, you must give it a try.

Equilibrium index of an Array using Array-Sum

In the array-sum approach, we first determine the array's overall sum. After that, go through the array and maintain updating the left sum which is initialised as zero. The items can be subtracted one at a time within the loop to obtain the correct sum.

Now let us see its implementation.

C++

#include <iostream>
using namespace std;
int equilibrium(int arr[], int n)
{
int total_sum = 0; // initialize sum of whole array
int leftsum = 0; // initialize leftsum
for (int i = 0; i < n; ++i) //finding total sum of array
     total_sum += arr[i];
for (int i = 0; i < n; ++i) {
     total_sum -= arr[i]; // sum is now right sum for index i
     if (leftsum == total_sum)
         return i;
     leftsum += arr[i];
}
return -1;
}
int main()
{
   int arr[] = { 1,7,3,6,5,6 };
   int arr_size = sizeof(arr) / sizeof(arr[0]);
   cout << "Equilibrium point is at index " << equilibrium(arr, arr_size) << endl;
   return 0;
}

C

#include <stdio.h>
int equilibrium(int arr[], int n)
{
   int total_sum = 0; // initialize sum of whole array
   int leftsum = 0; // initialize leftsum
   for (int i = 0; i < n; ++i) //finding total sum of array
       total_sum += arr[i];
   for (int i = 0; i < n; ++i) {
       total_sum -= arr[i]; // sum is now right sum for index i
       if (leftsum == total_sum)
           return i;
       leftsum += arr[i];
   }
   return -1;
}
int main()
{
   int arr[] = { 1,7,3,6,5,6 };
   int arr_size = sizeof(arr) / sizeof(arr[0]);
   printf("Equilibrium point is at index %d\n", equilibrium(arr, arr_size));
   return 0;
}

Java

public class Equilibrium {
   public static int equilibrium(int[] arr, int n) {
       int totalSum = 0; // initialize sum of whole array
       int leftSum = 0; // initialize leftsum
       for (int i = 0; i < n; i++) {
           totalSum += arr[i]; // finding total sum of array
       }
       for (int i = 0; i < n; i++) {
           totalSum -= arr[i]; // sum is now right sum for index i
           if (leftSum == totalSum) {
               return i;
           }
           leftSum += arr[i];
       }
       return -1;
   }
   public static void main(String[] args) {
       int[] arr = {1, 7, 3, 6, 5, 6};
       int arrSize = arr.length;
       int equilibriumIndex = equilibrium(arr, arrSize);
       if (equilibriumIndex != -1) {
           System.out.println("Equilibrium point is at index " + equilibriumIndex);
       } else {
           System.out.println("Equilibrium point not found.");
       }
   }
}

Python

def equilibrium(arr, n):
   total_sum = 0  # initialize sum of whole array
   leftsum = 0  # initialize leftsum
   # finding total sum of array
   for i in range(n):
       total_sum += arr[i]
   for i in range(n):
       total_sum -= arr[i]  # sum is now right sum for index i
       if leftsum == total_sum:
           return i
       leftsum += arr[i]
   
   return -1
# Driver code
arr = [1, 7, 3, 6, 5, 6]
arr_size = len(arr)
print(f"Equilibrium point is at index {equilibrium(arr, arr_size)}")

C#

using System;

class Program
{
    static int FindEquilibriumIndex(int[] arr)
    {
        int totalSum = 0; // Initialize sum of whole array
        int leftSum = 0; // Initialize left sum

        // Finding total sum of array
        foreach (int num in arr)
        {
            totalSum += num;
        }

        // Finding the equilibrium index
        for (int i = 0; i < arr.Length; i++)
        {
            totalSum -= arr[i]; // Sum is now right sum for index i
            if (leftSum == totalSum)
                return i;
            leftSum += arr[i];
        }

        return -1; // No equilibrium index found
    }

    static void Main()
    {
        int[] arr = { 1, 7, 3, 6, 5, 6 };
        int equilibriumIndex = FindEquilibriumIndex(arr);
        Console.WriteLine($"Equilibrium point is at index {equilibriumIndex}");
    }
}

JavaScript

function equilibrium(arr, n) {
   let total_sum = 0;  // initialize sum of whole array
   let leftsum = 0;  // initialize leftsum
   // finding total sum of array
   for (let i = 0; i < n; i++) {
       total_sum += arr[i];
   }
   for (let i = 0; i < n; i++) {
       total_sum -= arr[i];  // sum is now right sum for index i
       if (leftsum == total_sum) {
           return i;
       }
       leftsum += arr[i];
   }
   return -1;
}
// Driver code
let arr = [1, 7, 3, 6, 5, 6];
let arr_size = arr.length;
console.log(`Equilibrium point is at index ${equilibrium(arr, arr_size)}`);

Output

Equilibrium point is at index 3

Equilibrium index of an array using Prefix-Sum

Consider storing the prefix sum of the input array in an additional memory space called prefix[n], which keeps track of the total of all the items up to any given index i at prefix[i]. This is the prefix sum strategy. Now that we have this prefix array, we can quickly calculate the leftSum and rightSum in O(1) for each iteration of the outer loop.

C++

#include <iostream>
using namespace std;
int equilibrium(int arr[], int n)
{
   int prefix_sum[n];
   for(int i = 0; i < n; i++){
       if(i == 0)
           prefix_sum[i] = arr[i];
       else
           prefix_sum[i] = arr[i] + prefix_sum[i-1];
   }
   int total_sum = prefix_sum[n-1];
   for(int i = 0; i < n; i++){
       int left_sum = prefix_sum[i] - arr[i];
       int right_sum = total_sum - prefix_sum[i];
       if(left_sum == right_sum)
           return i;
   }
   return -1;
}
int main()
{
   int arr[] = { 1, 7, 3, 6, 5, 6 };
   int arr_size = sizeof(arr) / sizeof(arr[0]);
   cout << "Equilibrium point is at index " << equilibrium(arr, arr_size) << endl;
   return 0;
}

C

#include <stdio.h>
int equilibrium(int arr[], int n)
{
   int prefix_sum[n];
   for(int i = 0; i < n; i++){
       if(i == 0)
           prefix_sum[i] = arr[i];
       else
           prefix_sum[i] = arr[i] + prefix_sum[i-1];
   }
   int total_sum = prefix_sum[n-1];
   for(int i = 0; i < n; i++){
       int left_sum = prefix_sum[i] - arr[i];
       int right_sum = total_sum - prefix_sum[i];
       if(left_sum == right_sum)
           return i;
   }
   return -1;
}
int main()
{
   int arr[] = { 1, 7, 3, 6, 5, 6 };
   int arr_size = sizeof(arr) / sizeof(arr[0]);
   printf("Equilibrium point is at index %d\n", equilibrium(arr, arr_size));
   return 0;
}

Java

public class Main {
   public static int equilibrium(int[] arr, int n) {
       int[] prefixSum = new int[n];
       for (int i = 0; i < n; i++) {
           if (i == 0) {
               prefixSum[i] = arr[i];
           } else {
               prefixSum[i] = arr[i] + prefixSum[i - 1];
           }
       }
       int totalSum = prefixSum[n - 1];
       for (int i = 0; i < n; i++) {
           int leftSum = prefixSum[i] - arr[i];
           int rightSum = totalSum - prefixSum[i];
           if (leftSum == rightSum) {
               return i;
           }
       }
       return -1;
   }
   public static void main(String[] args) {
       int[] arr = {1, 7, 3, 6, 5, 6};
       int arrSize = arr.length;
       System.out.println("Equilibrium point is at index " + equilibrium(arr, arrSize));
   }
}

Python

def equilibrium(arr, n):
   prefix_sum = [0] * n
   for i in range(n):
       if i == 0:
           prefix_sum[i] = arr[i]
       else:
           prefix_sum[i] = arr[i] + prefix_sum[i-1]
   total_sum = prefix_sum[n-1]
   for i in range(n):
       left_sum = prefix_sum[i] - arr[i]
       right_sum = total_sum - prefix_sum[i]
       if left_sum == right_sum:
           return i
   return -1
arr = [1, 7, 3, 6, 5, 6]
arr_size = len(arr)
print("Equilibrium point is at index", equilibrium(arr, arr_size))

C#

using System;

class Program
{
    static int FindEquilibriumIndex(int[] arr)
    {
        int n = arr.Length;
        int[] prefixSum = new int[n];

        // Calculate prefix sums
        for (int i = 0; i < n; i++)
        {
            if (i == 0)
                prefixSum[i] = arr[i];
            else
                prefixSum[i] = arr[i] + prefixSum[i - 1];
        }

        int totalSum = prefixSum[n - 1];

        // Find the equilibrium index
        for (int i = 0; i < n; i++)
        {
            int leftSum = (i == 0) ? 0 : prefixSum[i] - arr[i];
            int rightSum = totalSum - prefixSum[i];
            if (leftSum == rightSum)
                return i;
        }

        return -1; // No equilibrium index found
    }

    static void Main()
    {
        int[] arr = { 1, 7, 3, 6, 5, 6 };
        int equilibriumIndex = FindEquilibriumIndex(arr);
        Console.WriteLine($"Equilibrium point is at index {equilibriumIndex}");
    }
}

JavaScript

function equilibrium(arr, n) {
 let prefixSum = new Array(n);
 for(let i = 0; i < n; i++) {
   if(i === 0) {
     prefixSum[i] = arr[i];
   } else {
     prefixSum[i] = arr[i] + prefixSum[i - 1];
   }
 }
 let totalSum = prefixSum[n - 1];
 for(let i = 0; i < n; i++) {
   let leftSum = prefixSum[i] - arr[i];
   let rightSum = totalSum - prefixSum[i];
   if(leftSum === rightSum) {
     return i;
   }
 }
 return -1;
}
let arr = [1, 7, 3, 6, 5, 6];
let arr_size = arr.length;
console.log("Equilibrium point is at index " + equilibrium(arr, arr_size));

Output

Equilibrium point is at index 3

Equilibrium index of an array using two pointers

In two pointers approach, we will keep track of the left_sum and right_sum while traversing the array itself. Let us see its implementation to understand it in a better way.

C++

#include <iostream>
using namespace std;
int equilibrium(int arr[], int n)
{
   int total_sum = 0;
   for(int i = 0; i < n; i++)
       total_sum += arr[i];
       
   int left_sum = 0;
   for(int i = 0; i < n; i++){
       int right_sum = total_sum - left_sum - arr[i];
       if(left_sum == right_sum)
          return i;
       left_sum += arr[i];
   }
   return -1;
}
int main()
{
   int arr[] = { 1, 7, 3, 6, 5, 6 };
   int arr_size = sizeof(arr) / sizeof(arr[0]);
   cout << "Equilibrium point is at index " << equilibrium(arr, arr_size) << endl;
   return 0;
}

C

#include <stdio.h>
int equilibrium(int arr[], int n)
{
   int total_sum = 0;
   for(int i = 0; i < n; i++)
       total_sum += arr[i];
       
   int left_sum = 0;
   for(int i = 0; i < n; i++){
       int right_sum = total_sum - left_sum - arr[i];
       if(left_sum == right_sum)
          return i;
       left_sum += arr[i];
   }
   return -1;
}
int main()
{
   int arr[] = { 1, 7, 3, 6, 5, 6 };
   int arr_size = sizeof(arr) / sizeof(arr[0]);
   printf("Equilibrium point is at index %d\n", equilibrium(arr, arr_size));
   return 0;
}

Java

public class Main {
   public static int equilibrium(int arr[], int n) {
       int total_sum = 0;
       for (int i = 0; i < n; i++) {
           total_sum += arr[i];
       }
       
       int left_sum = 0;
       for (int i = 0; i < n; i++) {
           int right_sum = total_sum - left_sum - arr[i];
           if (left_sum == right_sum) {
               return i;
           }
           left_sum += arr[i];
       }
       return -1;
   }
   public static void main(String[] args) {
       int arr[] = { 1, 7, 3, 6, 5, 6 };
       int arr_size = arr.length;
       System.out.println("Equilibrium point is at index " + equilibrium(arr, arr_size));
   }
}

Python

def equilibrium(arr):
   total_sum = sum(arr)
   left_sum = 0
   for i in range(len(arr)):
       right_sum = total_sum - left_sum - arr[i]
       if left_sum == right_sum:
           return i
       left_sum += arr[i]
   return -1
arr = [1, 7, 3, 6, 5, 6]
print("Equilibrium point is at index", equilibrium(arr))

C#

using System;

class Program
{
    static int FindEquilibriumIndex(int[] arr)
    {
        int n = arr.Length;
        int totalSum = 0;

        // Calculate total sum of the array
        for (int i = 0; i < n; i++)
            totalSum += arr[i];

        int leftSum = 0;

        // Find equilibrium index using the two-pointer approach
        for (int i = 0; i < n; i++)
        {
            int rightSum = totalSum - leftSum - arr[i];
            if (leftSum == rightSum)
                return i;

            leftSum += arr[i];
        }

        return -1; // No equilibrium index found
    }

    static void Main()
    {
        int[] arr = { 1, 7, 3, 6, 5, 6 };
        int equilibriumIndex = FindEquilibriumIndex(arr);
        Console.WriteLine($"Equilibrium point is at index {equilibriumIndex}");
    }
}

JavaScript

function equilibrium(arr) {
   let totalSum = 0;
   for(let i=0; i<arr.length; i++) {
       totalSum += arr[i];
   }
       
   let leftSum = 0;
   for(let i=0; i<arr.length; i++) {
       let rightSum = totalSum - leftSum - arr[i];
       if(leftSum == rightSum) {
          return i;
       }
       leftSum += arr[i];
   }
   return -1;
}
let arr = [1, 7, 3, 6, 5, 6];
console.log("Equilibrium point is at index " + equilibrium(arr));

Output

Equilibrium point is at index 3

Also read about - Equilibrium Index of an Array

Frequently Asked Questions

How do you find an equilibrium point?

Equilibrium point means that the index i at which the sum of the items at indices less than i equals the sum of the elements at indices greater than i is the equilibrium index of an array.

What is the equilibrium position point?

The "point" in "equilibrium position" is redundant. Equilibrium position itself refers to the specific location where the opposing forces balance out.

What is the equilibrium point?

An equilibrium point is a state where opposing forces or influences exactly cancel each other out, creating a condition of stability with no change.

What are the 3 types of equilibrium?

There are 3 equilibrium types: stable (returns if moved), unstable (moves further if moved), and neutral (no change if moved).

Conclusion

The equilibrium point represents a state of balance where opposing forces cancel each other out. It's a crucial concept in various fields, signifying stability and minimal change. Understanding the different types of equilibrium allows us to predict and analyze systems in science, economics, and even everyday life.

We hope you could take away critical techniques like analysing problems by walking over the execution of the examples and finding out the recursive pattern followed in most array problems.

Refer to our Guided Path to upskill yourself in DSA, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Code360.

Also check out the Interview guide for Product Based Companies as well as some of the Popular interview problems from top tech companies like Amazon, Adobe, Google, Uber, Microsoft, etc.