Find a Subarray With a Sum of 0

Given an array of integers, return true if some contiguous, non-empty subarray sums to 0.

Example 1

Text

Input:  [6, 4, -7, 3, 12, 9]
Output: true
Explanation: 4 + (-7) + 3 = 0

Example 2

Text

Input:  [1, 2, 3]
Output: false

Example 3

Text

Input:  [5, 0, 2]
Output: true   (the single element [0])

Brute force: every start, with a running sum

Fix a start index, then extend the end one element at a time while keeping a running sum. That checks every subarray without re-adding from scratch. The sum is a long, so a long array of large int values can't overflow it.

Java

public class Main {
    static boolean hasZeroSum(int[] nums) {
        for (int start = 0; start < nums.length; start++) {
            long sum = 0;
            for (int end = start; end < nums.length; end++) {
                sum += nums[end];
                if (sum == 0) return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(hasZeroSum(new int[]{6, 4, -7, 3, 12, 9}) + " " + hasZeroSum(new int[]{1, 2, 3}) + " " + hasZeroSum(new int[]{5, 0, 2}));
    }
}

Output

true false true

Time: O(n²). Space: O(1).

Optimal: repeated prefix sums

Let prefix[i] be the sum of the first i elements, with prefix[0] = 0. The sum of the subarray nums[i..j] is prefix[j] - prefix[i]. So:

A subarray sums to 0 exactly when two prefix sums are equal.

Walk the array, keep the running prefix sum, and store every prefix sum seen so far in a HashSet. If a prefix sum repeats, the elements between the two occurrences add up to 0. Start the set with 0, the prefix sum before any element, so a subarray that starts at index 0 is found too.

Walkthrough with [6, 4, -7, 3, 12, 9]:

index	x	prefix sum	seen before?	set after
start		0		{0}
0	6	6	no	{0, 6}
1	4	10	no	{0, 6, 10}
2	-7	3	no	{0, 6, 10, 3}
3	3	6	yes	return `true`

The prefix sum was 6 after index 0 and again after index 3, so nums[1..=3] = [4, -7, 3] sums to 0.

HashSet.add returns false when the value is already in the set, so one call both checks and inserts.

Java

import java.util.HashSet;
import java.util.Set;

public class Main {
    static boolean hasZeroSum(int[] nums) {
        Set<Long> seen = new HashSet<>();
        seen.add(0L);
        long prefix = 0;
        for (int x : nums) {
            prefix += x;
            if (!seen.add(prefix)) return true; // this prefix sum appeared before
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(hasZeroSum(new int[]{6, 4, -7, 3, 12, 9}) + " " + hasZeroSum(new int[]{1, 2, 3}) + " " + hasZeroSum(new int[]{5, 0, 2}));
        System.out.println(hasZeroSum(new int[]{-3, 3}) + " " + hasZeroSum(new int[]{}));
    }
}

Output

true false true
true false

Time: O(n). Space: O(n) for the set.

The sum uses long, so a long array of large int values can't overflow. The set holds Long objects, and 0L is needed because a plain 0 would box to an Integer, which never equals a Long.

Returning the subarray

Store the index where each prefix sum first occurred, and you can return the range as well. The method returns {start, end} with end exclusive, or null when no range exists.

Java

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main {
    static int[] zeroSumRange(int[] nums) {
        Map<Long, Integer> first = new HashMap<>(); // prefix sum -> position
        first.put(0L, 0);
        long prefix = 0;
        for (int i = 0; i < nums.length; i++) {
            prefix += nums[i];
            Integer start = first.get(prefix);
            if (start != null) return new int[]{start, i + 1};
            first.put(prefix, i + 1);
        }
        return null;
    }

    public static void main(String[] args) {
        int[] nums = {6, 4, -7, 3, 12, 9};
        int[] range = zeroSumRange(nums);
        System.out.println(range[0] + ".." + range[1] + " " + Arrays.toString(Arrays.copyOfRange(nums, range[0], range[1])));
        System.out.println(zeroSumRange(new int[]{1, 2, 3}) == null);
    }
}

Output

1..4 [4, -7, 3]
true

LeetCode 560 uses the same idea. A subarray ending at the current index sums to k when an earlier prefix sum equals prefix - k. Count how many times each prefix sum has occurred:

Java

import java.util.HashMap;
import java.util.Map;

public class Main {
    static int countSubarrays(int[] nums, int k) {
        Map<Long, Integer> counts = new HashMap<>();
        counts.put(0L, 1);
        long prefix = 0;
        int total = 0;
        for (int x : nums) {
            prefix += x;
            total += counts.getOrDefault(prefix - k, 0);
            counts.merge(prefix, 1, Integer::sum);
        }
        return total;
    }

    public static void main(String[] args) {
        System.out.println(countSubarrays(new int[]{1, 1, 1}, 2) + " " + countSubarrays(new int[]{1, 2, 3}, 3));
    }
}

Output

2 2

Edge cases

An element equal to 0: the prefix sum repeats immediately.
A prefix that sums to 0: found because the set starts with 0.
Empty array: false, since there are no non-empty subarrays.

Brute force: every start, with a running sum

Optimal: repeated prefix sums

Returning the subarray

Related: count subarrays that sum to k

Edge cases