# Zero sum subarray

Companies:

Given an array, find any subarray with sum as zero.

#### Example Test Cases

##### Sample Test Case 1

Input Array: 1, 2, -5, 3, -4,
Expected Output: 1, 3
Explanation: Since the sum of subarray b/w indices 1 and 3 is 0

##### Sample Test Case 2

Input Linked List: 1, 2, 3, 4, 5, 0, 6, 3
Expected Output: 5, 5

#### Solution

We can solve this problem by taking constructing a cumulative sum array and by using a hash table. Let the main array be called arr and cumulative sum array be called cu . cu will store the cumulative sum of all elements starting from position 0 till n - 1
Therefore, we can write: cu[k] = arr[0] + arr[1] + arr[2] + .... arr[k]
If the sum of subarray from index i + 1 till index j is 0, it means that cu[j] = cu[i] Therefore, we can create a hashmap with key as the sum and value as the index till which the sum was calculated, and check for duplicates.
See the below code for implementation.

#### Implementation

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

int main() {
vector vec = { 1, 2, -5, 3, 4 };

// map with key as runningTotal and value as index.
unordered_map mp;
int runningSum = 0;

pair zeroSumPositions(-1, -1);

for(int i = 0; i < vec.size(); i++) {
// calculate the cumulative total till this point.
runningSum += vec[i];

// If runningSum was seen before, it means we have a zero sum subarry.
if (mp.find(runningSum) != mp.end()) {
zeroSumPositions.first = mp[runningSum] + 1;
zeroSumPositions.second = i;
break;
}
else {
mp[runningSum] = i;
}
}
if (zeroSumPositions.first == -1) {
cout << "No zero sum subarray found!";
}
else {
cout << zeroSumPositions.first << ", " << zeroSumPositions.second << "\n";
}

return 0;
}
[gravityforms id="5" description="false" titla="false" ajax="true"]