Prefix Sum Technique

In an array of integers n, the prefix sum array is the array whose every element is the sum of all elements, of the original array, up to the current index.

Example:

Given an array of n=5 , array[]={1,2,3,4,5}
Its Prefix Sum array will be p[].
p[0]=array[0]=1;
p[1]=array[0]+array[1]=1+2=3;
p[2]=array[0]+array[1]+array[2]=1+2+3=6;
p[3]=array[0]+array[1]+array[2]+array[3]=1+2+3+4=10;
p[4]=array[0]+array[1]+array[2]+array[3]+array[4]=1+2+3+4+5=15;
Final Prefix Sum Array would be={1,3,6,10,15}

Approach : 

• To calculate the prefix sum array from any given array. we create a prefix array of the same size n. And initialize the first element to the array[0]. Because for the first element, the sum of elements up to 0 is an array of 0.

array[]={1,2,3,4,5}  prefix[]={1, , , , } //currently

• For index 1, Prefix[1] = prefix[0]+array[1] = 1+2=3, we run a loop through the original array and keep adding the prefix of [i-1],i.e,sum of all elements upto that index + array[current index]

array[]={1,2,3,4,5}  prefix[]={1, 3, , , }

• For index 2, prefix[2] = prefix[1]+array[2] = 3+3=6. In prefix[1] we have array[0]+array[1] and we add array[2] to it . So prefix[2] gives us sum of all elements upto array[2]

array[]={1,2,3,4,5}  prefix[]={1, 3,6 , , }

• For index 3, prefix[3] = prefix[2]+array[3] = 6+4=10. In prefix[2] we have array[0]+array[1]+array[2] and we add array[3] to it . So prefix[3] gives us sum of all elements upto array[3]

array[]={1,2,3,4,5}  prefix[]={1, 3,6 ,10 , }

• For index 4, prefix[4] = prefix[3]+array[4] = 10+5=15. In prefix[3] we have array[0]+array[1]+array[2] + array[3] and we add array[4] to it . So prefix[4] gives us sum of all elements upto array[4]

array[]={1,2,3,4,5}  prefix[]={1, 3,6 ,10 , 15}

Which gives us our final prefix array.

Code:

#include<iostream>

using namespace std;
int main() {
  int ar[5] = {1,2,3,4,5};
  int prefix[5];
  prefix[0] = ar[0]; //initializing first element
  for (int i = 1; i < 5; i++) {
    prefix[i] = prefix[i - 1] + ar[i];
  }
  for (int i = 0; i < 5; i++) {
    cout << prefix[i] << " "; //printing the array
  }
  return 0;
}

import java.util.*;

class TUF{
public static void main(String args[]) {
  int ar[] = {1,2,3,4,5};
  int prefix[]=new int[5];
  prefix[0] = ar[0]; //initializing first element
  for (int i = 1; i < 5; i++) {
    prefix[i] = prefix[i - 1] + ar[i];
  }
  for (int i = 0; i < 5; i++) {
    System.out.print(prefix[i]+" "); //printing the array
  }
  
}
}

Example problem Based on prefix sum technique

Problem Statement: Given an array of n integers, find if any index exists such that the sum of elements to its right is equal to the sum of elements to its left. If yes print the index, otherwise print “No Equilibrium”.

Examples:

Example 1:
Input: N = 5, array[] = {7,2,1,5,4} 
Output: 2
Explanation: Sum of elements to the left of index 2 is 7+2=9 and to the right of index 2 is 5+4=9. 

Example 2:
Input:  N=4, array[]={23,32,12,4} 
Output: No Equilibrium
Explanation: No such index exists for which the sum to its right and left is equal

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Brute Force Approach:

A basic approach to solve the above problem would be to run the first loop to traverse the whole array and then run 2 loops inside it one from 0 to the current index to calculate the left sum and one from the current index to n to calculate the right sum. Keep repeating this process till we find the required element.

Example:

N = 5, array[] = {7,2,1,5,4}

Here we run the first for loop with i to traverse all elements.Initially i=0, For array[i] , we run another for loop with j, from 0 to i-1 , to calculate left sum . And other for loop with k, from i+1 to n for right sum .

For i=0, j goes from 0 to  j<i , leftSum=0;
For i=0;k goes from k=i+1(1) to n , rightSum = 2+1+5+4=12

Since leftSum and rightSum are not equal loop continues and i=1.

Now , for i=1 
j goes from 0 to j<1 leftSum=7;
k  goes from 2 to n  rightSum = 1+5+4 = 10 

Since leftSum and rightSum are not equal loop continues and i=2.

Now , for i=2 
j goes from 0 to j<2 leftSum=7+2=9;
k  goes from 3 to n  rightSum = 5+4 = 9 

Since leftSum and rightSum  is equal we break here with ans = i = 2.

Code:

#include<iostream>
using namespace std;
int main(){
    int ar[5]={7,2,1,5,4};
    int ans=-1; //to store the final required index
    for(int i=0;i<5;i++){
        int leftSum=0,rightSum=0;
        for(int j=0;j<i;j++){
            leftSum+=ar[j];
        }
        for(int k=i+1;k<5;k++){
            rightSum+=ar[k];
        }
        if(leftSum == rightSum){
            ans=i;
            break;
        }
        
    }
    if(ans!=-1)cout<<ans<<" ";
    else{
        cout<<"NO EQILIBRIUM";
    }
    return 0;
}

import java.util.*;
class TUF{
public static void main(String args[]){
    int ar[]={7,2,1,5,4};
    int ans=-1; //to store the final required index
    for(int i=0;i<5;i++){
        int leftSum=0,rightSum=0;
        for(int j=0;j<i;j++){
            leftSum+=ar[j];
        }
        for(int k=i+1;k<5;k++){
            rightSum+=ar[k];
        }
        if(leftSum == rightSum){
            ans=i;
            break;
        }
        
    }
    if(ans!=-1)System.out.print(ans);
    else{
        System.out.println("NO EQILIBRIUM");
    }
}
}

Optimal Approach :

Using the prefix Sum technique, we can solve this in one pass, i.e, O(n).

We take the sum of the whole array and keep a left sum. For every index, we remove that index from the total sum and match it with the leftsum, if it is equal we break, otherwise add the current element to the leftsum and move forward.

Example:

N = 5, array[] = {7,2,1,5,4}
We initialize leftSum =0. Because for index =0 the leftSum is 0 totalSum for this array is 7+2+1+5+4=19

At index=0, leftSum=0 and  totalSum-array[index] = 19-7 = 12
Now leftSum and totalSum(which works as rightSum in this case) is not equal . We add array[index] to leftSum , leftSum =7 and  , move index++

At index=1, leftSum=7 and  totalSum-array[index] = 12-2 = 10
Now leftSum and totalSum(which works as rightSum in this case) is not equal . We add array[index] to leftSum , leftSum is 7+2=9 and move index++

At index=2, leftSum=9 and  totalSum-array[index] = 10-1 = 9
Now leftSum and totalSum is  equal . We save index as ans and break;

Code:

#include<iostream>

using namespace std;
int main() {
  int ar[5] = {7,2,1,5,4};
  int ans = -1; //to store the final required index
  int totalSum = 0;
  int leftSum = 0; //initialization
  for (int i = 0; i < 5; i++) {
    totalSum += ar[i];
  }
  for (int i = 0; i < 5; i++) {
    totalSum = totalSum - ar[i];

    if (leftSum == totalSum) {

      ans = i;
      break;
    }
    leftSum += ar[i];
  }

  if (ans != -1) cout << ans;
  else {
    cout << "NO EQUILIBRIUM";
  }
  return 0;
}

import java.util.*;

class TUF{
public static void main(String args[]) {
  int ar[] = {7,2,1,5,4};
  int ans = -1; //to store the final required index
  int totalSum = 0;
  int leftSum = 0; //initialization
  for (int i = 0; i < 5; i++) {
    totalSum += ar[i];
  }
  for (int i = 0; i < 5; i++) {
    totalSum = totalSum - ar[i];

    if (leftSum == totalSum) {

      ans = i;
      break;
    }
    leftSum += ar[i];
  }

  if (ans != -1) System.out.println(ans);
  else {
    System.out.println("NO EQUILIBRIUM");
  }
}
}

Special thanks to Rishika Gupta for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article