Coding · Hashing
Zero-Sum Subarrays
- Reported once
- Medium
- campus SDE (2021)
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
Given an array of integers that may contain negatives and zeros, count the contiguous, non-empty subarrays whose elements add up to exactly 0. Two subarrays at different positions count separately even when their values match. For [4,-4,1,-1,3] the answer is 3, from [4,-4], [1,-1] and [4,-4,1,-1]. The array can hold up to 100,000 values, each between -10^9 and 10^9 in size.
Restated in our own words, not a quote from Paytm or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: do I count the subarrays or only say whether one exists? Can values be negative or zero? Does a lone 0 count as a subarray? Are two subarrays with the same values at different positions counted twice? How long can the array be, and how big can the values get? What do I return for an empty array?
I would assume the task is to count, that a subarray is identified by its start and end positions, that a lone 0 counts, and that an empty array gives 0. With 100,000 values of size up to 10^9 the sums stay below 10^14, far under 2^53, and the answer, at most about five billion, also fits in a normal number.
Brute force
Say the obvious answer and why it is too slow.
Try every start. From each start, extend the end one element at a time while keeping a running sum, and count each time that sum is 0. That is O(n²) time and O(1) space. Re-adding every subarray from scratch would be O(n³), which is worse.
With n = 100,000 the double loop makes about five billion additions, far too slow for a normal time limit. The loop also throws away information: it never uses the fact that two positions with the same running total bound a zero-sum stretch, and nothing in it remembers totals it has already seen. A sliding window cannot fix it either, because negative values mean the sum does not move in one direction.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n²)
- Time
- O(n) average
- Space
- O(n)
The pattern is prefix sums with a hash map. Let P[i] be the sum of the first i elements, with P[0] = 0 for the empty prefix. The sum of the elements from position i up to j-1 is P[j] - P[i]. That is 0 exactly when P[j] equals P[i]. So counting zero-sum subarrays is the same as counting pairs of positions i < j whose prefix sums are equal.
Walk the array once and keep a map from each prefix value to how many times it has appeared so far. At each new prefix, every earlier position with the same prefix is the start of a different zero-sum subarray that ends right here, so add that stored count to the answer, then record the new prefix. The map must begin as {0: 1}, which stands for the empty prefix and lets a subarray that starts at the very first element be found.
Why it is correct: every subarray has exactly one end, and at that end the stored count equals the number of valid starts, so nothing is missed and nothing is counted twice. I would say it aloud as: a stretch sums to zero when the running total is the same before it and after it. The same idea gives subarrays summing to k by looking up prefix - k instead of prefix. Map reads and writes are O(1) on average, so the whole pass is O(n).
Walk it through
A dry run on the example, step by step.
| Step | Value | Prefix | Seen before | Total |
|---|---|---|---|---|
| start | - | 0 | - | 0 |
| 1 | 4 | 4 | 0 | 0 |
| 2 | -4 | 0 | 1 | 1 |
| 3 | 1 | 1 | 0 | 1 |
| 4 | -1 | 0 | 2 | 3 |
| 5 | 3 | 3 | 0 | 3 |
Use [4,-4,1,-1,3]. The trace table lists the running prefix after each value and how many times that prefix had already been seen before this step. That "seen before" number is exactly the count of zero-sum subarrays ending at this element.
Start with the map {0: 1}. After 4 the prefix is 4, new, so nothing is added. After -4 the prefix is back to 0, seen once, so one subarray ends here: [4,-4]. After 1 the prefix is 1, new. After -1 the prefix is 0 again and has been seen twice before, so two subarrays end here: [1,-1] and [4,-4,1,-1]. After 3 the prefix is 3, new. The total is 0 + 1 + 0 + 2 + 0 = 3.
The code
Runnable JavaScript, checked against test cases.
function countZeroSumSubarrays(nums) {
const seenCount = new Map([[0, 1]]);
let prefix = 0;
let total = 0;
for (const value of nums) {
prefix += value;
const earlier = seenCount.get(prefix) ?? 0;
total += earlier;
seenCount.set(prefix, earlier + 1);
}
return total;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
An empty array returns 0 because the loop body never runs. A single 0 returns 1: the prefix stays 0, and the seeded {0: 1} entry counts it. An array of zeros such as [0,0,0] returns 6, because the stored count for prefix 0 grows 1, 2, 3 and those values add up to 6.
All-positive arrays return 0, since every prefix is new. A whole array that cancels out, like [2,-2], is found through the seeded 0. Negative numbers need no special handling, since only equality of prefixes matters. Equal values at different positions are different pairs of positions, so they are counted separately. The count can reach n(n+1)/2, which is still safe in a JavaScript number for 100,000 elements.
Follow-ups to expect
Where the interviewer pushes next.
- How would you change the code to count subarrays whose sum is exactly k instead of 0?
- What if you must return the longest zero-sum subarray instead of the count, and what would the map store?
- If every value is positive and you want sums equal to k, can you drop the map, and what replaces it?
- How would the idea extend to a 2D grid, counting rectangles whose cells sum to zero?
- Could the count overflow in a language with 32-bit integers, and how would you guard against it?
Where candidates slip
The mistakes this problem punishes.
The most common slip is forgetting to seed the map with {0: 1}. Then every zero-sum subarray that begins at index 0 is missed, and [4,-4] returns 0.
Another is using a Set of seen prefixes. A Set can say "a zero-sum subarray exists" but cannot hold how many earlier positions share a prefix, so it adds one per match, and [0,0,0] would give 3 instead of 6. A third is recording the new prefix before reading its old count, which makes every position count itself and inflates the answer by n. People also reach for a sliding window out of habit from positive-only problems; with negatives it fails. Last, a quadratic double loop is fine for the first sketch but should not be the final answer at 100,000 elements.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.