82. Count Subarrays With Sum Zero

Given an array of n integers (which may include negatives), count the number of contiguous subarrays whose elements sum to exactly zero.

Input: The first line contains an integer n. The second line contains n space-separated integers, which may include negative numbers. Output: Print a single integer - the count of contiguous subarrays summing to exactly zero.

1 <= n <= 10^5

Don't forget to seed the hash map with prefix sum 0 occurring once BEFORE you start scanning - this correctly counts subarrays that start from index 0 itself and sum to zero, which would otherwise be missed.

Imagine a scoreboard that goes up when you gain points and down when you lose them. You want to know: how many different STRETCHES of the game ended with your score exactly back where a stretch started (net zero change)? That's exactly what this problem is asking, just with array elements instead of points. Brute force: Check every possible subarray (every start and end position combination) and add up its elements to see if the sum is zero. With n elements, there are about n²/2 subarrays, and summing each one directly takes up to O(n) time, so this brute force costs O(n³) in the worst case (or O(n²) if you cleverly reuse the running sum instead of re-adding from scratch each time). Optimised: The key trick: if the running total (prefix sum) up to two different points is IDENTICAL, then everything between those two points must have summed to exactly zero (since prefix_sum(j) - prefix_sum(i) = 0 means the elements from i+1 to j add up to 0). So instead of checking every subarray, just track how many times each prefix sum value has occurred using a hash map, and whenever a value repeats, add its previous occurrence count to your answer.

For every pair of start and end indices, recompute the sum of the elements between them from scratch by looping over that range, and count it if the sum is exactly zero. This directly checks the definition of a zero-sum subarray for every possible subarray, so it is trivially correct, but recomputing each sum independently means huge amounts of repeated addition work. Time: O(n^3) Space: O(1)

Maintain a running prefix sum while scanning the array once, and keep a hashmap counting how many times each prefix sum value has occurred so far (initialized with prefix sum 0 occurring once, to account for subarrays starting at index 0). A subarray from index i+1 to j sums to zero exactly when prefix[j] equals prefix[i], so every time the current prefix sum has already been seen c times, it contributes c new zero-sum subarrays ending at the current index; add that count and then increment the map. This turns the problem into a single linear pass with constant-time hashmap lookups. Time: O(n) Space: O(n)

For each starting index, extend the subarray one element at a time and keep a running sum instead of recomputing it from scratch, checking after each extension whether the running total is zero. This eliminates the innermost recomputation loop of the brute-force approach by reusing the previous partial sum, cutting the total work down by a full factor of n while still examining every subarray explicitly. Time: O(n^2) Space: O(1)

1. Walk through the array left to right, keeping a running total (prefix sum) as you go. 2. Write down every prefix sum you've seen so far, and how many times each value has occurred. 3. If the SAME prefix sum value shows up again later, everything between those two points summed to zero. 4. Count how many pairs of equal prefix sums exist - that count is your answer.

Time: One single pass through the array, doing a quick hash map lookup at each step - O(n) overall, dramatically faster than checking every possible subarray. Space: O(n) in the worst case, to store every distinct prefix sum value seen so far in the hash map.

n = 1 (a single zero-valued element), n = 10^5, and arrays with many repeated prefix sums (e.g. an array of all zeros) producing a large count.

This 'prefix sum + hash map' pattern is one of the single most reusable tricks in interview DSA - it also solves 'count subarrays with sum K' (not just zero) by checking for (current prefix sum - K) in the map instead of checking for a repeat of the current sum itself.