Prefix Sum And Kadane's Algorithm

Prefix Sum

A really common problem encountered in competitive programming can be solved using the concept of prefix sum. Given an array arr[] of size n, its prefix sum array is another array prefixSum[] of same size such that the value of prefixSum[i] is arr[0] + arr[1] + arr[2] … arr[i].

arr[] = {10, 20, 10, 5, 15}
prefixSum[] = {10, 30, 40, 45, 60}

Now this prefix sum array has various applications. For example, if you now want to the sum of all elements in the range [i,j], where i<=j, you could do it in just constant time (O(1)) by calculating prefixSum[j] - prefixSum[i-1]. This would otherwise take you linear time (O(N)), if you would have used the array by itself as you would have to traverse [i,j] each time.

Kadane's Algorithm

This easily transitions us to another really important concept: Kadane's Algorithm. Now, this technique is considered a DP algorithm but it's pretty easy to understand and is very handy when solving problems. This is used to find the Largest Sum Contiguous Subarray in a given array. Here is the problem statement, try to solve it on your own using what you've just learned (prefix sum). Maximum Subarray Sum

Here is the detailed implementation of Kadane's Algorithm.
You can also refer to this video to get a good understanding.

Application

Now, keeping this logic in mind lets try to solve a problem together. The problem's name is Subarray with zero sum and here is the problem statement:

Subarray with zero sum

So, whenever we try approaching a problem we forget all our tricks and algorithms and try to come up with a brute force solution. A simple solution to this problem would be to consider all subarrays one by one and check the sum of every subarray. We can run two loops: the outer loop picks a starting point i and the inner loop tries all subarrays starting from i. Time complexity of this method is O(N²).

Brute Force Solution (c++)

#include <bits/stdc++.h> 
using namespace std; 

/* Returns true if the there is a subarray  
of arr[] with sum equal to 'sum' otherwise  
returns false. Also, prints the result */
int subArraySum(int arr[], int n) 
{ 
    int curr_sum, i, j; 

// Pick a starting point 
for (i = 0; i < n; i++) { 
    curr_sum = arr[i]; 

    // try all subarrays starting with 'i' 
    for (j = i + 1; j <= n; j++) { 
        if (curr_sum == 0) { 
            cout << "Sum found between indexes "
                 << i << " and " << j - 1; 
            return 1; 
        } 
        if (curr_sum > 0 || j == n) 
            break; 
        curr_sum = curr_sum + arr[j]; 
    } 
} 

cout << "No subarray found"; 
return 0; 
}

// Driver Code 
int main() 
{ 
    int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
   
    subArraySum(arr, n); 
    return 0; 
} 

We can optimize this our answer using hashing. The idea is to iterate through the array and for every element arr[i], calculate sum of elements form 0 to i (this can simply be done as sum += arr[i]). If the current sum has been seen before, then there is a zero sum array. Hashing is used to store the sum values, so that we can quickly store sum and find out whether the current sum is seen before or not.

For example:

arr[] = {1, 4, -2, -2, 5, -4, 3}

If we consider all prefix sums, we can
notice that there is a subarray with 0
sum when :
1) Either a prefix sum repeats or
2) Or prefix sum becomes 0.

Prefix sums for above array are:
1, 5, 3, 1, 6, 2, 5

Since prefix sum 1 repeats, we have a subarray
with 0 sum. 

Optimized Solution (c++)

#include <bits/stdc++.h> 
using namespace std; 

bool subArrayExists(int arr[], int n) 
{ 
unordered_set<int> sumSet; 

// Traverse through array and store prefix sums 
int sum = 0; 
for (int i = 0 ; i < n ; i++) 
{ 
    sum += arr[i]; 

    // If prefix sum is 0 or it is already present 
    if (sum == 0 || sumSet.find(sum) != sumSet.end()) 
        return true; 

    sumSet.insert(sum); 
} 
return false; 
} 

// Driver code 
int main() 
{ 
int arr[] =  {-3, 2, 3, 1, 6}; 
int n = sizeof(arr)/sizeof(arr[0]); 
if (subArrayExists(arr, n)) 
    cout << "Found a subarray with 0 sum"; 
else
    cout << "No Such Sub Array Exists!"; 
return 0; 
}  

To get a better understanding of the concept you could attempt this similar question.