Zero Sum Subarray

Tags

Zero Sum Subarray

Category

Arrays

Difficulty

Medium

Problem Statement

Given an array of integers, determine whether any contiguous subarray sums to zero. A subarray of length 1 that is zero counts, and the empty subarray (sum 0 trivially) does not count.

Intuition

If the running prefix sum at index j equals the prefix sum at some earlier index i, then the subarray from i+1 to j sums to zero. Equivalently, if the prefix sum itself is zero at any point, the subarray from the start to that index sums to zero. By storing prefix sums in a set, we can detect a repeat (or a zero) in constant time per element.

Approach

  1. Initialize a set containing 0 (to detect subarrays starting from index 0).
  2. Maintain a running prefixSum = 0.
  3. For each element in the array:
    • Add the element to prefixSum.
    • If prefixSum is already in the set, return true.
    • Add prefixSum to the set.
  4. If the loop completes without finding a repeat, return false.

Pseudocode

function zeroSumSubarray(array):
    sums = set containing {0}
    prefixSum = 0

    for num in array:
        prefixSum += num
        if prefixSum in sums:
            return true
        sums.add(prefixSum)

    return false

Time & Space Complexity

  • Time: O(n) — single pass with O(1) average hash set operations.
  • Space: O(n) — the set can store up to n+1 prefix sums.

Key Insights

  • Seeding the set with 0 elegantly handles subarrays that start at index 0 without special-casing.
  • This prefix-sum technique generalizes: to find a subarray summing to any target k, check if prefixSum - k is in the set.
  • The problem only asks for existence, not the actual subarray indices, which simplifies the solution.

Edge Cases

  • Array contains a zero: immediately returns true (subarray of length 1).
  • Empty array: no subarray exists, return false.
  • All positive or all negative numbers with no zero: return false unless prefix sums collide.
  • Single element equal to zero: return true.
  • Single non-zero element: return false.

Linked mentions