Posts Equilibrium Index of an Array
Post
Cancel

Equilibrium Index of an Array

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];

:exclamation: 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;
        
    }
}
This post is licensed under CC BY 4.0 by the author.