Subarray with sum equal to 0
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
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;}