Print all subarrays with 0 sum

The problem, simply

You get an array of whole numbers. Some are positive, some negative, some zero. Find every subarray (an unbroken stretch of the array) whose numbers add up to 0. Print each one by its start and end index.

There can be many answers, and they can overlap. You must list them all, in any order.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every start. From each start, walk to the right and keep a running sum. Each time the sum is 0, print the stretch.

1. For each start from 0 to n - 1, set sum = 0.
2. For each end from start to n - 1, add arr[end] to sum.
3. If sum == 0, record (start, end).

class Solution {
    public List<int[]> zeroSumSubarrays(int[] arr) {
        List<int[]> out = new ArrayList<>();
        for (int start = 0; start < arr.length; start++) {
            long sum = 0;
            for (int end = start; end < arr.length; end++) {
                sum += arr[end];                     // grow the stretch by one
                if (sum == 0) out.add(new int[]{start, end});
            }
        }
        return out;
    }
}

How long it takes: about n * n / 2 stretches, O(n^2). Extra room: nothing besides the answers, O(1).

Way 2: the clever way

Keep the running total, the prefix sum. If the total after index i equals the total after index j (with i < j), then the numbers from i + 1 to j add to 0.

1. Make a map from each total to the list of indices where it appeared. Put total 0 at index -1 first: that stands for "before the array starts", so stretches that begin at index 0 are found too.
2. Walk the array and update the total.
3. For every earlier index p in the list of the current total, record the stretch (p + 1, i).
4. Add i to the list for the current total.

class Solution {
    public List<int[]> zeroSumSubarrays(int[] arr) {
        List<int[]> out = new ArrayList<>();
        Map<Long, List<Integer>> seen = new HashMap<>();
        seen.computeIfAbsent(0L, z -> new ArrayList<>()).add(-1);  // before the start
        long total = 0;
        for (int i = 0; i < arr.length; i++) {
            total += arr[i];
            List<Integer> earlier = seen.computeIfAbsent(total, z -> new ArrayList<>());
            for (int p : earlier) out.add(new int[]{p + 1, i});    // each match is one answer
            earlier.add(i);
        }
        return out;
    }
}

How long it takes: one walk with map lookups is O(n), plus one step for each of the k answers, O(n + k). There can be up to n^2 / 2 answers (all zeros), and then nothing can beat printing them all. Extra room: the map, O(n).

Watch out for

• Storing only the first or last index for each total finds some answers but not all. To print every stretch you need every index.
• Totals can overflow int on long arrays of big numbers. Use long keys.
• The answer for p in the list is (p + 1, i), not (p, i). The number at p itself is not part of the stretch.

What interviewers ask next

• Just check whether any zero stretch exists. Use a set of totals: return true as soon as a total repeats or equals 0. O(n).
• Count the zero stretches without printing. Keep a count per total instead of a list, and add the count each time. O(n) even when there are n^2 stretches.
• The longest zero stretch. Store only the first index of each total, and measure i - first[total].
• Stretches that add to K instead of 0. Look up total - K instead of total. This is the famous "subarray sum equals K".
• Longest stretch with equal numbers of 0s and 1s. Turn every 0 into -1, then find the longest zero stretch.

Remember this

Grown-up words: the diary totals are prefix sums, the index at the back of the diary is a hash map from prefix sum to positions, a stretch is a subarray, and O(n + k) is output sensitive time.