Find equilibrium index of an array

Coding Interview Problem

Difficulty Level

Medium

Asked In

Amazon, Adobe, Hike

Three solutions Discussed

1. Brute force approach — Using two loops)
2. An iterative approach using extra space — Using Prefix Sum array
3. Using an incremental approach — Single Scan using variables

Key takeaway after reading this blog

This is a good coding interview problem to learn — how to optimize space complexity and solve the problem using a single scan. We can find a lot of similar problems asked during the coding interview.

Let’s understand the problem

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

• In other words, the equilibrium index of an array is an index i such that the sum of elements at indices less than i is equal to the sum of elements at indices greater than i. Element at index i is not included in either part.

A[0] + A[1]+….. + A[i-1] = A[i+1] + ….. + A[n-1], Where 0 < i < n-1

• It is stated that at max there is only one equilibrium index in the array. Return the index if it is present otherwise return -1.
• Values in the input array can be repeated.

Examples

Input: A[] = [-7, 1, 5, 2, -4, 3, 0]
Output: 3
Explanation: 3 is an equilibrium index, because:
A[0] + A[1] + A[2] = A[4] + A[5] + A[6]
Input: A[] = [0, 1, 3, -2, -1]
Output: 1
Explanation: 1is an equilibrium index, because: 
A[0] = A[2] + A[3] + A[4]

Brute force approach — Using two nested loops

Algorithm Idea

A straightforward method is to use two loops. The idea is to find the sum of elements for every range of indexes and observe if there exists an equilibrium index. The outer loop traverses the array, and the inner loop determines if there is an equilibrium index or not. For this we can use two extra variables —

• leftSum — sum of all elements which is left of the current index
• rightSum — sum of all elements which is right of the current index

Algorithm Steps

• Declare variables leftSum and righSum
• Run a loop through the array from 0 to n-1. For each index i, find the sum of elements towards the left and right of the current index. If the leftSum and rightSum are equal, then the current index is the equilibrium index.
• return -1 by end of the loop because we did not find the equilibrium index.

Algorithm Pseudocode

int equilibriumIndex(int A[], int n)
{
    int leftSum, int rightSum 
    for(i = 0; i < n; i = i + 1)
    {
        leftSum = 0
        for(j = 0; j < i; j = j + 1)
            leftSum = leftSum + A[i]
        
        rightSum = 0
        for(j = i + 1; j < n; j = j + 1)
            rightSum = rightSum + A[i]
     
        if(leftSum == rightSum)
            return i 
    }        
    return -1        
}

Algorithm Analysis

We are running nested loops and calculating left_sum and right_sum for every value of i. Total number of summation operation = n(n-1) (Think!)

Time Complexity = O(n²), Space Complexity: O(1)

An iterative approach using extra space — Using prefix sum array

Algorithm Idea

The idea is to store the prefix sum of the array. The prefix sum would help keep track of the sum of all elements up to any index of the array. Now, we should find a way to keep track of the sum of values to the left and right of the current index. For this we can use additional temporary variables totalSum to store sum of all elements of the array.

Algorithm Steps

• Declare prefix sum array of size n
• Scan the array using loop and store prefix sum of the array

for(i = 0; i < n; i = i + 1)
{
    if(i == 0)
        prefix[i] = A[i]
    else 
        prefix[i] = A[i] + prefix[i-1]
}

• Get the total sum of the array in variable totalSum i.e totalSum = prefix[n-1]
• Iterate through the array and calculate variables leftSum and rightSum. If we subtract prefix[i] from value at current index i, we will get the value of leftSum. Similarly, if If we subtract totalSum from prefix[i], we will get the value of rightSum. Now, compare both leftSum and rightSum to find whether the current index is the equilibrium index or not. If leftSum equals rightSum, return the current index i.

for(i = 0; i < n; i = i + 1)
{
    int leftSum = prefix[i] - A[i]
    int rightSum = totalSum - prefix[i]
    if(leftSum == rightSum)
        return i
}

• return -1 by end of the loop because we did not find the equilibrium index.

Algorithm Pseudocode

int equilibriumIndex(int A[], int n)
{
    int prefix[n]
    for(i = 0; i < n; i = i + 1)
    {
        if(i == 0)
            prefix[i] = A[i]
        else 
            prefix[i] = A[i] + prefix[i-1]
    }
    
    int totalSum = prefix[n-1]
    for(i = 0; i < n; i = i + 1)
    {
        int leftSum = prefix[i] - A[i]
        int rightSum = totalSum - prefix[i]
        if(leftSum == rightSum)
            return i
    }
    return -1        
}

Algorithm Analysis

We are running two separate loops for calculating the prefix sum array and equilibrium index respectively. Time Complexity = Time complexity of calculating prefix sum array + Time complexity of calculating Equilibrium Index = O(n) + O(n) = O(n)

Space Complexity: The above algorithm uses extra space to create a prefix sum array. Hence, the space complexity would be O(n).

Using an incremental approach — Single scan using variables

Algorithm Idea

The motive is to get the total sum of the array first. The difference between the above method and this method is that we don’t need to store the prefix sum beforehand. Instead, we will keep track of the leftSum and rightSum while traversing the array itself.

Algorithm Steps

• Declare and initialise the variables totalSum and leftSum
• Now run a loop to store the total sum of the array in variable totalSum

for(i = 0; i < n; i = i + 1)
    totalSum = totalSum + A[i]

• Iterate through the array and keep track of the variables leftSum and rightSum. If leftSum equals rightSum, we return the current index i. Think about the calculation of variables in the following loop —

for(i = 0; i < n; i = i + 1)
{
    totalSum = totalSum - A[i]
    int rightSum = totalSum - leftSum
    if(leftSum == rightSum)
        return i
    int leftSum = leftSum + A[i]
}

• return -1 by end of the loop because we did not find the equilibrium index.

Algorithm Pseudocode

int equilibriumIndex(int A[], int n)
{
    int totalSum = 0
    int leftSum = 0
    for(i = 0; i < n; i = i + 1)
        totalSum = totalSum + A[i]
        
    for(i = 0; i < n; i = i + 1)
    {
        totalSum = totalSum - A[i]
        int rightSum = totalSum - leftSum
        if(leftSum == rightSum)
            return i
        int leftSum = leftSum + A[i]
    }
    return -1
}

Algorithm Analysis

We are running two separate loops for calculating the total sum and equilibrium index respectively. Time complexity = Time complexity of calculating prefix sum array + Time complexity of calculating Equilibrium Index = O(n) + O(n) = O(n)

Space Complexity = O(1), because we are just using variables to store the value of total, left, and right sum.

Possible questions by the Interviewer

• Can we solve this problem using the hash table?
• Can we solve this problem using two pointer approach?
• How to modify the above code if there can be multiple equilibrium indexes? What would be the different corner cases?

Problems for practice using a single scan

• Remove duplicates from sorted array
• A Product Array Puzzle
• Valid Mountain
• Chocolate Distribution Problem
• Best Time to Buy and Sell Stock
• Partition the array into three equal sum segments
• Sort an array in the waveform
• The maximum difference between two elements such that larger element appears after the smaller number
• Number of jumps for a thief to cross walls
• Find the number of subarrays with even sum
• Double the first element and move zero to end

Reviewer: Shubham Gautam (https://shubhamsuper30.medium.com)

If you have any ideas/queries/doubts/feedback, please comment below or write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy coding, Enjoy algorithms!