Finding Equilibrium index in an array

Problem Statement: Finding Equilibrium index in an array

Given a 0-indexed integer array nums, find the leftmost equilibrium Index.

An equilibrium Index is an index at which sum of elements on its left is equal to the sum of element on its right. That is, nums[0] + nums[1] + … + nums[equilibriumIndex-1] == nums[equilibriumIndex+1] + nums[equilibriumIndex+2] + … + nums[nums.length-1]. If equilibriumIndex == 0, the left side sum is considered to be 0. Similarly, if equilibriumIndex == nums.length – 1, the right side sum is considered to be 0.

Return the leftmost equilibrium Index that satisfies the condition, or -1 if there is no such index.

Examples:

Example 1:
Input: nums = [2,3,-1,8,4]
Output: 3
Explanation: The sum of the numbers before index 3 is: 2 + 3 + -1 = 4
The sum of the numbers after index 3 is: 4 = 4

Example 2:
Input: nums = [1,-1,4]
Output: 2
Explanation: The sum of the numbers before index 2 is: 1 + -1 = 0
The sum of the numbers after index 2 is: 0

Solution:

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Using Two Loops(Brute Force)

Consider two variables leftSum and rightSum initialized to zero.Now for every index, i calculate the leftSum till that index and rightSum till that index.

At any point if (leftSum == rightSum) return that index i.

If equilibrium index not found return -1.

Code:

C++ Code

#include <iostream>
using namespace std;
int findEquilibriumIdx(int nums[], int n) {
  int leftSum, rightSum;
 
  for (int i = 0; i < n; i++) {
    leftSum = 0;
    for (int j = 0; j < i; j++) {
      leftSum += nums[j];
    }
    rightSum = 0;
    for (int j = i + 1; j < n; j++) {
      rightSum += nums[j];
    }
    if (leftSum == rightSum) {
      return i;
    }
  }
  return -1;
}
int main() {
  int n = 5;
  int arr[] = { 2, 3, -1, 8, 4 };
  int equilibriumidx = findEquilibriumIdx(arr, n);
  cout << equilibriumidx << endl;
  return 0;
}

Output: 3

Time Complexity: O(N^2)

Space Complexity: O(1)

Java Code

import java.util.*;
 
class Main {
  public static int findEquilibriumIdx(int nums[], int n) {
    int leftSum, rightSum;
 
    for (int i = 0; i < n; i++) {
      leftSum = 0;
      for (int j = 0; j < i; j++) {
        leftSum += nums[j];
      }
      rightSum = 0;
      for (int j = i + 1; j < n; j++) {
        rightSum += nums[j];
      }
      if (leftSum == rightSum) {
        return i;
      }
    }
    return -1;
  }
  public static void main(String[] args) {
    int n = 5;
    int nums[] = { 2, 3, -1, 8, 4};
    int equilibriumidx = findEquilibriumIdx(nums, n);
    System.out.println(equilibriumidx);
 
  }
}

Output: 3

Time Complexity: O(N^2)

Space Complexity: O(1)

Solution 2: Using Total Sum

Calculate the sum = total sum of all the integers in the array.

Keep leftSum = 0, rightSum = sum.

leftSum = sum of all the integers to its left

rightSum = sum of all the integers to it’s right.

At every index i rightSum would be rightSum excluding the current index value.now we will is Check if(leftSum == rightSum) If yes then return that index else keep moving forward.while moving forward it can be seen that we are considering that current index value to be on left so update the leftSum value. leftSum = leftSum + nums[i].

If no such index is found return -1.

Code:

C++ Code

#include <iostream>
 
using namespace std;
int findEquilibriumIdx(int nums[], int n) {
  int totalSum = 0;
  for (int i = 0; i < n; i++) {
    totalSum += nums[i];
  }
  int leftSum = 0, rightSum = totalSum;
  for (int i = 0; i < n; i++) {
    rightSum -= nums[i];
    if (leftSum == rightSum) {
      return i;
    }
    leftSum += nums[i];
  }
  return -1;
}
int main() {
  int n = 5;
  int arr[] = {2, 3, -1, 8, 4};
  int equilibriumidx = findEquilibriumIdx(arr, n);
  cout << equilibriumidx << endl;
  return 0;
}

Output: 3

Time Complexity: O(N)

Space Complexity: O(1)

Java Code

import java.util.*;
 
class Main {
  public static int findEquilibriumIdx(int nums[], int n) {
    int totalSum = 0;
    for (int i = 0; i < n; i++) {
      totalSum += nums[i];
    }
    int leftSum = 0, rightSum = totalSum;
    for (int i = 0; i < n; i++) {
      rightSum -= nums[i];
      if (leftSum == rightSum) {
        return i;
      }
      leftSum += nums[i];
    }
    return -1;
  }
  public static void main(String[] args) {
    int n = 5;
    int nums[] = {2, 3, -1, 8, 4};
    int equilibriumidx = findEquilibriumIdx(nums, n);
    System.out.println(equilibriumidx);
 
  }
}

Output: 3

Time Complexity: O(N)

Space Complexity: O(1)

Special thanks to P.C.Bhuvaneshwari for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article