Problem Description
Check if there is any index for which the sum of all elements on the left side equals sum of all elements on the right. Equilibrium Index of an Array
Solution
We can make use of prefix array to solve this optimally. Fist, we initialize the prefix array. For every i from 0 to N-1, we get the sum on the left and sum of the right using the prefix array.
LeftSum = prefix[i-1];
rightSum = prefix[n-1] - prefix[i];
Edge case: for i=0, handle leftSum separately.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
String equilibrium(int arr[], int n) {
int prefix[] = new int[n];
prefix[0] = arr[0];
for(int i=1; i<n; i++){
prefix[i] = prefix[i-1] + arr[i];
}
int leftSum = 0;
int rightSum = 0;
String output="NO";
for(int i=0; i<n; i++){
if(i==0){
leftSum = 0;
}else{
leftSum = prefix[i-1];
}
rightSum = prefix[n-1] - prefix[i];
if(leftSum == rightSum){
output = "YES";
break;
}
}
return output;
}
}