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; }