Prefix sum problems: Given an array find Equilibrium Index

Problem Statement:

You are given an array, you need to find Equilibrium Index.

Equilibrium Index meaning, an index such that the sum of all elements at lower index equal to the sum of all the elements at higher index.

Example:

Input: arr[] = [1, 2, 0, 3]

Output: 2

Explanation: The sum of left of index 2 is 3 and the sum of right of index 2 is 3

Solution 1: Brute force approach

In this solution we will use 2 nested loops.

Outer loop iterates through all index one by one.

Inner index finds if the index i is Equilibrium by checking leftt sum == right sum

Time Complexity: O(n*n)
Space Complexity: O(1)

Solution 2: Prefix and suffix sum

Calculate the prefix sum and suffix sum.

Then check for each index, if any prefix sum == suffix sum and print the result.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

int solution_1(vector<int>& nums) 
{
  
    for (int i = 0; i < nums.size(); i++) 
    {
        int leftSum = 0;
        int rightSum = 0;


        for (int j = 0; j < i; j++) 
        {
            leftSum += nums[j];
        }

        for (int j = i + 1; j < nums.size(); j++) 
        {
            rightSum += nums[j];
        }

        if (leftSum == rightSum) 
        {
            return i;  
        }
    }

    return -1;  
}


int solution_2(vector<int>& nums) 
{
    int prefix_sum  = 0;

    for(int i= 0; i < nums.size(); i++)
    {
        prefix_sum += nums[i];
    }

    int left_sum =0; 
    int right_sum = prefix_sum ;

    for(int i= 0; i < nums.size(); i++)
    {
        right_sum = right_sum - nums[i];

        if(left_sum == right_sum)
            return i;
        
        left_sum += nums[i];
    }
    return -1;
}

int main()
{
    vector<int> arr =  {1, 2, 0, 3};
  
    cout << solution_1(arr)<<endl;
    
    cout << solution_2(arr)<<endl;
    return 0;
}

Output

2