Find All Subarrays with Zero Sum

Title: Find All Subarrays with Zero Sum

In this guide, you’ll learn how to find every contiguous subarray of an integer array whose elements sum to zero. This is a frequent Java interview question because the brute-force solution is easy to write but slow, and the efficient solution tests whether you understand prefix sums and hash maps.

We’ll walk through the approach, build a complete Java program, trace it on a sample input, and then cover the common mistakes, edge cases, and follow-up questions an interviewer is likely to raise.

Understanding the Problem

A subarray is a contiguous run of elements from the original array, unlike a subsequence which can skip elements. Given an array arr of integers, the goal is to find every pair of indices (start, end) such that the elements from arr[start] to arr[end] add up to exactly 0.

The straightforward approach checks every possible (start, end) pair and sums the elements between them, which costs O(n^2) time. The prefix sum technique you’ll build here finds the same answer in a single O(n) pass by recognizing that a subarray sums to zero exactly when two prefix sums are equal.

Approach

1. Initialize an empty List<int[]> to collect the resulting subarrays and a HashMap<Integer, List<Integer>> to map every prefix sum seen so far to the indices where it occurred.
2. Seed the map with 0 mapped to a list containing -1, so a subarray that starts at index 0 and sums to zero is still detected.
3. Iterate through the array while maintaining a running sum that adds arr[i] at each index i.
4. Before recording the current index, check whether sum already exists as a key in the map.
5. If it does, every index stored under that key marks the start of a zero-sum subarray ending at i; add each (startIndex + 1, i) pair to the result list.
6. Append the current index i to the list of indices stored under sum, using computeIfAbsent so existing indices for that sum are preserved.
7. After the loop finishes, the result list contains every zero-sum subarray as a pair of start and end indices.
8. Print or return the result list for the caller to use.

Java Program

import java.util.*;

public class ZeroSumSubarrays {

    public static List<int[]> findZeroSumSubarrays(int[] arr) {
        List<int[]> result = new ArrayList<>();
        Map<Integer, List<Integer>> prefixSumIndices = new HashMap<>();
        prefixSumIndices.put(0, new ArrayList<>(List.of(-1)));

        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (prefixSumIndices.containsKey(sum)) {
                for (int startIndex : prefixSumIndices.get(sum)) {
                    result.add(new int[]{startIndex + 1, i});
                }
            }
            prefixSumIndices.computeIfAbsent(sum, k -> new ArrayList<>()).add(i);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, -3, 1, 6};
        List<int[]> subarrays = findZeroSumSubarrays(arr);

        if (subarrays.isEmpty()) {
            System.out.println("No zero-sum subarray found");
        } else {
            for (int[] range : subarrays) {
                System.out.println("Subarray from index " + range[0] + " to " + range[1]);
            }
        }
    }
}

Explanation of the Program

• prefixSumIndices maps every running sum seen so far to the list of indices where that sum occurred, seeded with 0 mapped to -1 so a zero-sum subarray starting at index 0 is still caught.
• The loop updates sum by adding arr[i] on every iteration, then checks whether that exact sum has already been seen.
• Every stored index under the current sum marks the start of a zero-sum subarray ending at index i, so the method records a result for each one, not just the first.
• computeIfAbsent appends the current index to the existing list for sum instead of overwriting it, which is what allows the same prefix sum to produce multiple zero-sum subarrays.
• main runs the method on a sample array and prints each discovered subarray as a start and end index, or a message when none exist.

Step-by-Step Trace

Trace the algorithm on arr = [1, 2, -3, 4, -4, 5], where the goal is to find every zero-sum subarray:

At the end of each iteration, sum holds the prefix sum of arr[0..i], and prefixSumIndices maps every prefix sum seen so far to every index at which it occurred.

Examples

Example 1: No Zero-Sum Subarray

An array of only positive numbers can never contain a zero-sum subarray, because the running sum only increases and never repeats.

int[] arr = {1, 2, 3, 4, 5};
List<int[]> result = findZeroSumSubarrays(arr);
// Output:
// No zero-sum subarray found

Example 2: Multiple Overlapping Zero-Sum Subarrays

When the same prefix sum repeats more than twice, the same ending index can close more than one zero-sum subarray.

int[] arr = {3, -3, 1, -1, 5};
List<int[]> result = findZeroSumSubarrays(arr);
// Output:
// Subarray from index 0 to 1
// Subarray from index 0 to 3
// Subarray from index 2 to 3

Common Mistakes to Avoid

These are the mistakes candidates most often make when implementing this approach:

• Forgetting to seed the map with sum 0 – misses every subarray that starts at index 0 and sums to zero, since there is no earlier index to pair it with. Initialize prefixSumIndices with 0 mapped to -1 before the loop starts.
• Overwriting the index list for a sum – using put(sum, List.of(i)) instead of appending replaces the earlier indices for that sum and silently loses zero-sum subarrays that should have been found. Use computeIfAbsent and add to the existing list.
• Checking for a match after inserting the current index – inserting i before checking containsKey(sum) makes every index match itself, reporting a zero-length subarray that doesn’t exist. Always check for the sum first, then insert the index.
• Stopping at the first match in the index list – returning only prefixSumIndices.get(sum).get(0) instead of looping over the whole list misses the other zero-sum subarrays that share the same prefix sum. Iterate over every stored index.
• Using startIndex instead of startIndex + 1 – reporting the subarray as starting at the matched prefix index instead of one past it includes an extra element, so the reported range no longer actually sums to zero.

Edge Cases to Test

Before you call this solved, make sure the implementation handles these input shapes:

• Empty array
• Single-element array equal to zero
• Single-element non-zero array
• All positive elements (no zero-sum subarray exists)
• All negative elements
• Entire array sums to zero
• Multiple overlapping zero-sum subarrays sharing the same prefix sum
• Large positive and negative values that risk overflowing int when accumulated

Additional Considerations

Building prefixSumIndices and scanning the array takes O(n) time, since each HashMap lookup and insert is O(1) on average. The space cost is also O(n) in the worst case, when every prefix sum is distinct.

The number of zero-sum subarrays returned can itself be O(n^2) in the worst case, for example an alternating array like [1, -1, 1, -1, ...] where the same prefix sum repeats at roughly half the indices. Collecting and printing every pair then dominates the running time even though building the map stays linear.

Use long sum instead of int sum if the array can contain large values whose running total might overflow a 32-bit integer.

Interview Follow-up Questions

Once you’ve nailed the base solution, expect an interviewer to push further with questions like these:

• What if you only need to know whether any zero-sum subarray exists? – return true the moment the running sum repeats or equals zero, without collecting every match.
• What if you need the longest zero-sum subarray instead of all of them? – keep only the first index at which each prefix sum was seen, then track the maximum of i - firstIndex as you scan.
• What if the input array is read-only and you cannot use extra data structures? – fall back to the O(n^2) brute-force check of every (start, end) pair’s sum directly, since the HashMap approach inherently needs O(n) auxiliary space.
• What if the array arrives as a stream of unknown length? – maintain the running sum and the prefix sum map incrementally per element, reporting a match the moment a repeated sum appears, so memory grows with distinct prefix sums rather than total elements seen.
• What if the data is partitioned across multiple machines? – compute each shard’s prefix sums locally, then pass the last running sum of each shard to the next shard as an offset; subarrays crossing a shard boundary need the boundary prefix sums exchanged between adjacent workers.

Conclusion

Finding all zero-sum subarrays comes down to recognizing that two equal prefix sums bracket a subarray that sums to zero, which turns an O(n^2) brute-force scan into a single O(n) pass with a HashMap. The same prefix sum idea extends directly to the more general problem of finding subarrays that sum to any target k, just by checking for sum - k instead of sum in the map.

Try adapting the program above to return the actual subarray contents instead of just the indices, or to find only the longest zero-sum subarray. You can learn more about array-based problems in the Arrays category on DailyJavaConcept.