Print all subarrays with 0 sum

Problem Statement

Given an array of integers, print all subarrays with 0 sum. A subarray is a contiguous part of the array.

Constraints:

• Array can contain positive, negative, and zero values
• Print/return all subarrays, not just count

Example:

• Input: arr = [6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7]
• Output:
  • Subarray from index 2 to 4 ([-1, -3, 4])
  • Subarray from index 2 to 6 ([-1, -3, 4, -2, 2])
  • Subarray from index 5 to 6 ([-2, 2])
  • Subarray from index 6 to 9 ([2, 4, 6, -12])
  • Subarray from index 0 to 10 (entire array)

Approach 1: Brute Force (Check All Subarrays)

Intuition

Generate all possible subarrays and check if their sum equals zero.

Algorithm

1. For each starting index i
2. For each ending index j >= i
3. Calculate sum of subarray [i, j]
4. If sum is 0, add to result

import java.util.*;

public class Solution {
    public List<int[]> findZeroSumSubarrays(int[] arr) {
        List<int[]> result = new ArrayList<>();
        int n = arr.length;
        
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += arr[j];
                if (sum == 0) {
                    result.add(new int[]{i, j});
                }
            }
        }
        
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n²) - Nested loops (with O(n³) if sum calculated freshly)
• Space Complexity: O(k) - Where k is number of zero-sum subarrays

Approach 2: Using Prefix Sum and HashMap (Optimal)

Intuition

If prefix sum at index j equals prefix sum at index i, then subarray (i+1, j) has sum 0. Use a hashmap to store all indices where each prefix sum occurs.

Key Insight

Also, if prefixSum[i] == 0, then subarray (0, i) has sum 0.

Algorithm

1. Calculate running prefix sum
2. Use hashmap: prefix_sum -> list of indices where this sum occurred
3. If prefix_sum is 0, subarray from start to current index has sum 0
4. If prefix_sum seen before, we have zero-sum subarrays ending at current index

import java.util.*;

public class Solution {
    public List<int[]> findZeroSumSubarrays(int[] arr) {
        List<int[]> result = new ArrayList<>();
        int n = arr.length;
        
        // Map: prefix_sum -> list of indices
        Map<Integer, List<Integer>> prefixSumIndices = new HashMap<>();
        
        int prefixSum = 0;
        
        for (int i = 0; i < n; i++) {
            prefixSum += arr[i];
            
            // Subarray starting from index 0
            if (prefixSum == 0) {
                result.add(new int[]{0, i});
            }
            
            // Check if this prefix sum was seen before
            if (prefixSumIndices.containsKey(prefixSum)) {
                for (int prevIdx : prefixSumIndices.get(prefixSum)) {
                    result.add(new int[]{prevIdx + 1, i});
                }
            }
            
            // Store current index for this prefix sum
            prefixSumIndices.computeIfAbsent(prefixSum, k -> new ArrayList<>()).add(i);
        }
        
        return result;
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n + k) where k is number of subarrays
• Space Complexity: O(n) - HashMap storage

Just Count Zero-Sum Subarrays

Variation: Find Longest Zero-Sum Subarray

Key Takeaways

1. Prefix Sum Property: If prefix sums at indices i and j are equal, sum of subarray (i+1, j) is 0
2. HashMap Storage: Store all indices for each prefix sum to find all subarrays
3. Count vs Print: Storing counts is simpler; storing indices needed to print subarrays
4. Zero Prefix Sum: Don't forget subarrays starting from index 0
5. Time Complexity: O(n) for counting, O(n + k) for printing all k subarrays
6. Applications: Finding balanced parentheses, equal 0s and 1s subarrays