Zero Sum Subarray

We have given an array arr[] of size n. Our task is to find the total count of sub-arrays having their sum equal to 0.

Example 1

Input:

n = 6

arr[] = {0,0,5,5,0,0}

Output: 6

Explanation: The 6 subarrays are

[0], [0], [0], [0], [0,0], and [0,0].

Example 2

Input:

n = 10

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

We are using a HashMap to store the prefix sum of subarrays encountered so far along with their frequency. As we traverse the array, we calculate the prefix sum by adding each element. If the current prefix sum is zero, it indicates that we have found a subarray with a sum of zero, so we increment the count. If the prefix sum is already present in the HashMap, it means there exists a subarray with a sum of zero between the current index and the index where the same prefix sum was encountered previously. In such cases, we add the frequency of that prefix sum to the count. Finally, we return the total count of subarrays with a sum of zero.

1. Initialize a HashMap to store the prefix sum and its frequency.
2. Initialize variables prefixSum and count to keep track of the prefix sum and the count of subarrays with sum zero, respectively.
3. Traverse the array and calculate the prefix sum by adding each element.
4. Check if the prefix sum is zero, if so, increment the count.
5. If the prefix sum is already present in the HashMap, increment the count by its frequency.
6. Increment the frequency of the prefix sum in the HashMap.
7. After traversing the array, return the final count.

Complexity

• Time Complexity: O(n), where n is the size of the input array.
• Space Complexity: O(n), where n is the size of the input array.

Code

# Java Code

import java.util.*;

public class ZeroSumSubarrays {

    static int findSubarrays(int[] arr, int n) {
        // Map to store prefix sum and its frequency
        Map<Integer, Integer> map = new HashMap<>();
        int prefixSum = 0, count = 0;

       
        // Traverse the array and calculate prefix sum
        for (int i = 0; i < n; i++) {
            prefixSum += arr[i];

            // If prefix sum is zero, increment count
            if (prefixSum == 0)
                count++;

            // If prefix sum is already present in map, increment count by its frequency
            if (map.containsKey(prefixSum))
                count += map.get(prefixSum);

            // Increment frequency of prefix sum
            map.put(prefixSum, map.getOrDefault(prefixSum, 0) + 1);
        }
        return count;
    }

    public static void main(String[] args) {
        int[] arr1 = {0, 0, 5, 5, 0, 0};
        int n1 = arr1.length;
        System.out.println("Output for Example 1: " + findSubarrays(arr1, n1)); // Output: 6

        int[] arr2 = {6, -1, -3, 4, -2, 2, 4, 6, -12, -7};
        int n2 = arr2.length;
        System.out.println("Output for Example 2: " + findSubarrays(arr2, n2)); // Output: 4
    }
}

Output

Output for Example 1: 6

Output for Example 2: 4