Difficulty: Easy, Asked-in: Amazon, Adobe, Hike

Key takeaway: An excellent problem to learn problem-solving and step-by-step optimization using loop and variables.

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 the sum of elements at lower indexes is 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.

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

Problem note

• For i = 0, we assume that the sum of elements at lower indexes is equal to 0.
• For i = n - 1, we assume that the sum of elements at higher indexes is equal to 0.

Example 1

Input: A[ ] = [-7, 1, 5, 2, -4, 3, 0], Output: 3

Explanation: 3 is an equilibrium index i.e. A[0] + A[1] + A[2] = A[4] + A[5] + A[6] = -1

Example 2

Input: A[ ] = [0, 1, 3, -2, -1], Output: 1

Explanation: 1 is an equilibrium index i.e. A[0] = A[2] + A[3] + A[4] = 0

Example 3

Input: A[ ] = [1, 2, -2, -1], Output: -1

Explanation: There is no such equilibrium index in the array.

Important note: before moving on to the solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. Enjoy problem-solving!

Follow-up questions

• Candidate: For calculating the equilibrium index, Do we need to include index i in the left or right part? Interviewer: No, the element at index i is not included in either part.
• Candidate: Is there a possibility of a multiple equilibrium index? Interviewer: No, 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.
• Candidate: Are the input values only positive? Interviewer: No, It may be positive, negative, or zero.
• Candidate: Are the input values unique? Interviewer: No, it can be repeated.

Discussed solution approaches

• A brute force approach using nested loops
• Using prefix sum array and a single loop
• An efficient approach using a single loop

A brute force approach using two nested loops

Solution idea

The basic idea is to explore each index i and find the sum of all elements on the left and right sides, excluding the value at index i. If both left and right sums are equal, then index i would be the equilibrium index.

We can use nested loops to implement this: the outer loop explores each index i, and the inner loop determines index i is an equilibrium index or not by calculating the left and right sums. We can use two extra variables: leftSum and rightSum to store the sum of elements on the left and right side of the current index.

Solution steps

1. We declare variables leftSum and righSum.
2. Now we run a loop from i = 0 to n-1. Inside the loop, we find the sum of elements towards the left and right sides of the current index.

3. We initialize leftSum equal to 0 and run a loop from j = 0 to i - 1 to calculate the leftSum.

   for(int j = 0; j < i; j = j + 1)
     leftSum = leftSum + A[j]
   

4. We initialize rightSum equal to 0 and run a loop from j = i + 1 to n - 1 to calculate the rightSum.

   for(int j = i + 1; j < n; j = j + 1)
     rightSum = rightSum + A[j]
   

5. If the leftSum and rightSum are equal, then the current index i is the equilibrium index and we return i as an output.

   if(leftSum == rightSum)
    return i
   

6. By the end of the outer loop, we return -1 because we did not find any such equilibrium index.

Solution pseudocode

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

Solution analysis

We are running nested loops and calculating leftSum and rightSum for every index i. Inside the outer loop, the summation is the critical operation that will define our time complexity.

• The first inner loop run from j = 0 to i - 1. Total summation operation = i
• The second inner loop run from j = i + 1 to n - 1. Total summation operation = n - i - 1
• Total summation operation at each iteration of the outer loop = i + n - i - 1 = n - 1
• Here outer loop is running n times, so overall count of the summation operation = n(n - 1) = O(n²). Time complexity = O(n²).
• We are using constant extra space, so space complexity = O(1)

Using prefix sum array and a single loop

Now the critical question is: can we improve the time complexity further? Can we do some pre-processing to avoid the repeated calculations of leftSum and rightSum at each outer loop iteration? Think!

Solution idea

Suppose we store the prefix sum of the input array in an extra memory prefix[n], which keeps track of the sum of all elements up to any index i at prefix[i]. Now using this prefix array, at each iteration of the outer loop, we can easily calculate the leftSum and rightSum in O(1). How? Think!

• If we subtract the prefix[i] with the value at the current index i, then we can easily get the value of leftSum. leftSum = prefix[i] - A[i]
• Now, we should find a way to keep track of the sum of elements to the right of the current index i. The idea is simple: if we subtract the total sum of all array elements with the prefix[i], we will get the value of the rightSum. We can use a temporary variable totalSum to store the sum of all array elements, which is equal to the prefix[n]. rightSum = totalSum - prefix[i]
• Now, we compare both leftSum and rightSum to find whether the current index is the equilibrium index or not.

Solution steps

• We declare prefix sum array of size n.
• Now we traverse the array to store the prefix sum.

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

• We initialize a variable totalSum to store the total sum of the array i.e totalSum = prefix[n-1]
• Now we run a loop from i = 0 to n-1 and calculate the values of leftSum and rightSum at each iteration. If leftSum equals rightSum, we return the current index i.

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

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

Solution pseudocode

int equilibriumIndex(int A[], int n)
{
    int prefix[n]
    for (int 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 (int 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        
}

Solution analysis

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

The above solution uses extra space to store the prefix sum array. Hence, the space complexity would be O(n).

An efficient in-place idea using a single loop

Now again the critical question is: can we improve the space complexity and solve the problem without using a prefix array? Can we track the values of leftSum and rightSum while traversing the array itself? Think!

Solution idea

Before starting the ith iteration of the loop, suppose we know the totalSum and the value of the leftSum. Then at ith iteration:

• We can easily update the rightSum which is equal to the totalSum - leftSum -A[i].
• Now we check if leftSum and rightSum are equal or not. If yes, then we return index i as an output. Otherwise, we move to the next iteration.
• Before moving to the next iteration, we update the leftSum for the next iteration i.e. leftSum = leftSum + A[i].

Solution steps

• We initialize the variables totalSum and leftSum with 0.
• We run a loop to store the total sum of the array in the variable totalSum.

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

• Now we iterate through the array and keep track of the variables leftSum and rightSum and check whether the current index is the equilibrium index or not.

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

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

Solution pseudocode

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

Solution analysis

We are running two separate loops for calculating the total sum and equilibrium index, respectively. So time complexity = Time complexity of calculating the total sum + Time complexity of finding the equilibrium index = O(n) + O(n) = O(n). Space complexity = O(1), we only use variables to store the total, left, and right sum.

Important note: we recommend transforming the above pseudo-codes into a favorite programming language (C, C++, Java, Python, etc.) and verifying all the test cases. Enjoy programming!

Critical ideas to think about!

• Can we solve this problem using the hash table?
• Can we solve this problem using two pointers approach?
• Can we try to solve this problem using some other approach?
• If there can be multiple equilibrium indexes, How to modify the above code to return all the equilibrium indexes? What would be the different corner cases?
• In the efficient approach, why are calculating leftSum after the comparison if(leftSum == rightSum)?

Comparison of time and space complexities

• Brute force approach: Time = O(n²), Space = O(1)
• Using prefix sum array: Time = O(n), Space = O(n)
• Using single loop: Time = O(n), Space = O(1)

Suggested coding problems to practice

• Number of buildings facing the sun
• Remove duplicates from the sorted array
• Chocolate Distribution Problem
• Sort an array of 0s, 1s and 2s
• Find minimum and maximum in an array
• Move zeroes to an end
• Product of Array Except Self
• Sort an array in a waveform

Thanks to Navtosh Kumar for his contribution to the content. Please write in the message below if you find anything incorrect, or if you want to share more insight. Enjoy learning, Enjoy algorithms!