# 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;
}```
Scroll to Top

### Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.