Zero sum subarray

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