Print all subarrays with sum 0

Medium

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): []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}