Subarray with sum equal to 0

Easy

Problem

Given an array of integers (it may contain negatives), return true if some non-empty contiguous subarray sums to 0.

Example 1

Input:  [4, 2, -3, 1, 6]
Output: true

[2, -3, 1] sums to 0.

Example 2

Input:  [4, 2, 0, 1, 6]
Output: true

The single element [0].

Example 3

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

Also asked as: Find if there is any subarray with sum equal to 0

Test cases

Case 1

Input:    [4,2,-3,1,6]
Expected: true

Case 2

Input:    [4,2,0,1,6]
Expected: true

Case 3

Input:    [-3,2,3,1,6]
Expected: false

Case 4

Input:    []
Expected: false

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Prefix sums in a set

Time O(n)Space O(n)

If the running prefix sum repeats (or is 0), the elements in between sum to 0.

function hasZeroSumSubarray(a) {
const seen = new Set([0]);
let sum = 0;
for (const x of a) {
sum += x;
if (seen.has(sum)) return true;
seen.add(sum);
}
return false;
}