Array Basics to Advance

In this article, we will learn about how to find the total count of all zero sub array, in the given question.

Problem Statement

We are given an array, and we need Find the total count of subarrays with their sum equal to 0.

Examples:

Input: arr[] = [0, 0, 5, 5, 0, 0]
Output: 6
Explanation: The 6 subarrays are [0], [0], [0], [0], [0,0], and [0,0].

Input: arr[] = [6, -1, -3, 4, -2, 2, 4, 6, -12, -7]
Output: 4
Explanation: The 4 subarrays are [-1, -3, 4], [-2, 2], [2, 4, 6, -12], 
and [-1, -3, 4, -2, 2]

✅ Approach 1: Gathering all Subarrays

In this approach, we will gather all possible subarray, and count that subarray that will give me the value as zero.

one for loop will be use to traverse all subarrays, and another for loop will be used for calculating sum of subarrays.

class Solution {
  public:
    int findSubarray(vector<int> &arr) {
        // code here.
        int ans=0;
        int sum=0;
        int n=arr.size();
        for(int i=0;i<n;i++){
            sum=0;
            for(int j=i;j<n;j++){
                sum+=arr[j];
                if(sum==0)
                    ans++;
            }
        }
        return ans;
    }
};

Time Complexity: O(n^2)

Space Complexity: O(1)

✅ Approach 2: Use HashMap

To solve this efficiently, we use the prefix sum concept along with a hash map to keep track of how many times a particular prefix sum has occurred.

Get Mayur777’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The idea is:

• If the sum of elements from index 0 to i is the same as the sum from 0 to j, it means the elements between (j+1 to i) sum up to zero.
• So, if the same prefix sum repeats, a zero-sum subarray exists between those positions.

1. Traverse the array and keep calculating the cumulative sum.
2. Use a map (mp) to store how many times each prefix sum has occurred.
3. If a prefix sum appears again, it indicates the existence of a zero-sum subarray, and we add its frequency to our answer.

int findSubarray(vector<int> &arr) {
    long long int ans = 0;
    int n = arr.size();
    map<long long int, int> mp;

    // Initializing map with 0 sum occurring once
    mp[0]++;

    long long int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];

        // If this sum has been seen before, we found subarrays summing to 0
        if (mp.find(sum) != mp.end())
            ans += mp[sum];

        // Record this sum
        mp[sum]++;
    }

    return ans;
}

🧪 Dry Run Example

Let’s dry run the code with an example input:

vector<int> arr = {1, -1, 2, -2, 3};

We keep track of sum and a map mp:

| Index | Element | sum | `mp[sum]` before | Subarrays added to ans | ans |
| ----- | ------- | --- | ---------------- | ---------------------- | --- |
| 0     | 1       | 1   | 0                | 0                      | 0   |
| 1     | -1      | 0   | 1 (initial)      | 1                      | 1   |
| 2     | 2       | 2   | 0                | 0                      | 1   |
| 3     | -2      | 0   | 2 (already seen) | 2                      | 3   |
| 4     | 3       | 3   | 0                | 0                      | 3   |

✅ So, the final answer is 3, which are the subarrays:

• {1, -1}
• {2, -2}
• {1, -1, 2, -2}