Print all subarrays with sum 0
Problem
Print the start and end index of every contiguous subarray whose sum is 0.
Example 1
Input: [6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7] Output: (2,4), (2,6), (5,6), (6,9), (0,10)
Also asked as: print all subarrays with 0 sum
Test cases
Case 1
Input: [6,3,-1,-3,4,-2,2,4,6,-12,-7] Expected (any order): [[2,4],[2,6],[5,6],[6,9],[0,10]]
Case 2
Input: [1,-1,1,-1] Expected (any order): [[0,1],[1,2],[2,3],[0,3]]
Case 3
Input: [0] Expected (any order): [[0,0]]
Case 4
Input: [1,2,3] Expected (any order): []
View solutionHide solution1 approach
1. Prefix sum → list of indices
Time O(n) + outputSpace O(n)
Map each prefix sum to all indices where it occurs. Any two indices with the same prefix sum bound a zero-sum subarray.
function zeroSumSubarrays(a) { const map = new Map([[0, [-1]]]); let sum = 0; const res = []; for (let i = 0; i < a.length; i++) { sum += a[i]; if (map.has(sum)) for (const start of map.get(sum)) res.push([start + 1, i]); if (!map.has(sum)) map.set(sum, []); map.get(sum).push(i); } return res;}