Find if there is any subarray with sum equal to 0

The problem, simply

You get an array of whole numbers, some may be negative. Is there a stretch of boxes next to each other (a subarray) whose numbers add up to exactly 0? Answer true or false.

The stretch can be any length from one box to the whole array.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every start. From each start, keep adding boxes to the right and check if the total hits 0.

1. For each start i, set sum = 0.
2. For each end j from i on, add arr[j]. If sum == 0, return true.
3. If nothing hits 0, return false.

class Solution {
    public boolean hasZeroSum(int[] arr) {
        for (int i = 0; i < arr.length; i++) {          // start of the stretch
            int sum = 0;
            for (int j = i; j < arr.length; j++) {      // grow it one box at a time
                sum += arr[j];
                if (sum == 0) return true;
            }
        }
        return false;
    }
}

How long it takes: about n * n / 2 stretches, O(n^2). Extra room: one total, O(1).

Way 2: the clever way

Keep a running total, called the prefix sum. If the total after box j equals the total after an earlier box i, then the boxes i + 1 to j added nothing, so they sum to 0.

1. Put 0 in a notebook (a hash set) first. It stands for "before any box".
2. Walk the array and add each number to sum.
3. If sum is already in the notebook, return true.
4. Otherwise write sum in the notebook and move on.

The animation keeps the box number next to each total, so you can see which stretch it is.

class Solution {
    public boolean hasZeroSum(int[] arr) {
        Map<Long, Integer> seen = new HashMap<>();   // running total -> box after which we saw it
        seen.put(0L, -1);                            // height 0 before any box
        long sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            Integer before = seen.get(sum);
            if (before != null) {
                // boxes before + 1 .. i add up to 0
                return true;
            }
            seen.put(sum, i);
        }
        return false;
    }
}

How long it takes: one walk with one notebook check per box, O(n) on average. Extra room: up to n + 1 totals in the notebook, O(n).

Watch out for

• Running totals can overflow an int when the numbers are large. A long total is safer.
• Store the first box where each total appeared, and do not overwrite it. That gives the longest zero stretch if you need it.
• Sorting the array does not help: it destroys which boxes are next to each other.

What interviewers ask next

• Return the stretch itself. The map already knows: it is from before + 1 to i.
• Longest stretch with sum 0? Keep the first box of each total and take the biggest i - before.
• How many stretches sum to 0? Store how many times each total has appeared, and add that count every time you see it again.
• Stretches that sum to k instead of 0? Look up sum - k instead of sum. Same O(n) idea.
• What if all numbers are positive? Then totals only grow, so no repeat is possible unless there is a 0 in the array. For "sum to k" with positive numbers a sliding window works with O(1) extra room.

Remember this

Grown-up words: the height after each step is a prefix sum, the notebook is a hash set (or a hash map from sum to index), and a stretch of boxes next to each other is a subarray.