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.
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
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!
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.
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]
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]
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
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
}
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.
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!
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!
for(int i = 0; i < n; i = i + 1)
{
if(i == 0)
prefix[i] = A[i]
else
prefix[i] = prefix[i-1] + A[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
}
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
}
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).
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!
Before starting the ith iteration of the loop, suppose we know the totalSum and the value of the leftSum. Then at ith iteration:
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]
}
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
}
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!
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!
Given an array X[] of distinct elements, write a program to find all the unique triplets in the array whose sum is equal to zero. For example, suppose such triplets in the array are X[i], X[j] and X[k] then X[i] + X[j] + X[k] = 0. Note : solution set must not contain duplicate triplets.
Given an array A[] of integers, find out the maximum difference between any two elements such that the larger element appears after the smaller element. In other words, we need to find max(A[j] - A[i]), where A[j] > A[i] and j > i. This is an excellent problem to learn problem-solving using divide and conquer, transform and conquer and a single loop.
Quicksort is often the best practical choice for sorting because it works remarkably efficiently on average O(nlogn) time complexity. It is also one of the best algorithms to learn problem-solving using recursion and divide and conquer approach. In this blog, we have covered: 1) How quick sort works recursively? 2) Choosing a correct pivot value in the partition algorithm 3) Best, worst, and average-case time complexity analysis 4) Space complexity and essential properties of the quick sort. Explore and Enjoy!
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.