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