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. For example, in an array A:
Example :
Input: A[] = {-7, 1, 5, 2, -4, 3, 0}
Output: 3
3 is an equilibrium index, because:
A[0] + A[1] + A[2] = A[4] + A[5] + A[6]Input: A[] = {1, 2, 3}
Output: -1
Write a function int equilibrium(int[] arr, int n); that given a sequence arr[] of size n, returns an equilibrium index (if any) or -1 if no equilibrium indexes exist.
Method 1 (Simple but inefficient)
Use two loops. Outer loop iterates through all the element and inner loop finds out whether the current index picked by the outer loop is equilibrium index or not. Time complexity of this solution is O(n^2).
Python3
# Python program to find equilibrium # index of an array# function to find the equilibrium indexdef equilibrium(arr): leftsum = 0 rightsum = 0 n = len(arr) # Check for indexes one by one # until an equilibrium index is found for i in range(n): leftsum = 0 rightsum = 0 # get left sum for j in range(i): leftsum += arr[j] # get right sum for j in range(i + 1, n): rightsum += arr[j] # if leftsum and rightsum are same, # then we are done if leftsum == rightsum: return i # return -1 if no equilibrium index is found return -1 # driver codearr = [-7, 1, 5, 2, -4, 3, 0]print (equilibrium(arr))# This code is contributed by Abhishek Sharama |
3
Time Complexity: O(n^2)
Auxiliary space: O(1)
Method 2 (Tricky and Efficient)
The idea is to get the total sum of the array first. Then Iterate through the array and keep updating the left sum which is initialized as zero. In the loop, we can get the right sum by subtracting the elements one by one. Thanks to Sambasiva for suggesting this solution and providing code for this.
1) Initialize leftsum as 0
2) Get the total sum of the array as sum
3) Iterate through the array and for each index i, do following.
a) Update sum to get the right sum.
sum = sum - arr[i]
// sum is now right sum
b) If leftsum is equal to sum, then return current index.
// update leftsum for next iteration.
c) leftsum = leftsum + arr[i]
4) return -1
// If we come out of loop without returning then
// there is no equilibrium index
The image below shows the dry run of the above approach:
Below is the implementation of the above approach:
Python3
# Python program to find the equilibrium# index of an array# function to find the equilibrium indexdef equilibrium(arr): # finding the sum of whole array total_sum = sum(arr) leftsum = 0 for i, num in enumerate(arr): # total_sum is now right sum # for index i total_sum -= num if leftsum == total_sum: return i leftsum += num # If no equilibrium index found, # then return -1 return -1 # Driver codearr = [-7, 1, 5, 2, -4, 3, 0]print ('First equilibrium index is ', equilibrium(arr))# This code is contributed by Abhishek Sharma |
First equilibrium index is 3
Output:
First equilibrium index is 3
Time Complexity: O(n)
Space Complexity: O(1)
Method 3 :
This is a quite simple and straightforward method. The idea is to take the prefix sum of the array twice. Once from the front end of array and another from the back end of array.
After taking both prefix sums run a loop and check for some i if both the prefix sum from one array is equal to prefix sum from the second array then that point can be considered as the Equilibrium point.
Python3
# Python program to find the equilibrium# index of an array# Function to find the equilibrium indexdef equilibrium(arr): left_sum = [] right_sum = [] # Iterate from 0 to len(arr) for i in range(len(arr)): # If i is not 0 if(i): left_sum.append(left_sum[i-1]+arr[i]) right_sum.append(right_sum[i-1]+arr[len(arr)-1-i]) else: left_sum.append(arr[i]) right_sum.append(arr[len(arr)-1]) # Iterate from 0 to len(arr) for i in range(len(arr)): if(left_sum[i] == right_sum[len(arr) - 1 - i ]): return(i) # If no equilibrium index found,then return -1 return -1# Driver codearr = [-7, 1, 5, 2, -4, 3, 0]print('First equilibrium index is ', equilibrium(arr))# This code is contributed by Lokesh Sharma |
First equilibrium index is 3
Time Complexity: O(N)
Auxiliary space: O(N)
Please refer complete article on Equilibrium index of an array for more details!
