S2Q1 · Largest Zero Sum Subarray

📁 GitHub

⚡ Quick Reference

Function: largest_zero_sum_subarray(nums: list) -> list

Core idea: use a prefix sum hash map - if the same prefix sum appears twice, the subarray between those two positions sums to zero.

def largest_zero_sum_subarray(nums: list) -> list:
    prefix = {0: -1}   # prefix_sum → first index where it occurred
    total  = 0
    best_start, best_len = 0, 0

    for i, x in enumerate(nums):
        total += x
        if total in prefix:
            length = i - prefix[total]
            if length > best_len:
                best_len   = length
                best_start = prefix[total] + 1
        else:
            prefix[total] = i

    return nums[best_start : best_start + best_len]

Key rules: - prefix[sum] = index stores the first occurrence of each prefix sum - If prefix[total] already exists, nums[prev+1 : i+1] sums to zero - Keep the longest such subarray; ties → first occurrence wins - Return [] if no zero-sum subarray found

---

Problem Statement

Problem

Write a function largest_zero_sum_subarray(nums) that returns the longest contiguous subarray with sum zero. If multiple subarrays share the maximum length, return the first one. Return [] if none exists.

Example:

Input

[3, 4, -7, 1, 2, -3]

Output

[3, 4, -7, 1, 2, -3]

---

Understanding the problem

A subarray is a contiguous slice. We need the longest one that sums to zero.

Brute force (O(n²)) - check every subarray:

for i in range(n):
    for j in range(i+1, n+1):
        if sum(nums[i:j]) == 0: ...

This works but is slow for large inputs.

Prefix sum trick (O(n)) - the key insight:

If the prefix sum at index i equals the prefix sum at index j (where i < j), then the subarray from i+1 to j sums to zero.

prefix sums of [3, 4, -7, 1, 2, -3]:

index:       -1   0   1   2   3   4   5
value:         -   3   4  -7   1   2  -3
prefix sum:    0   3   7   0   1   3   0
                        ↑           ↑
                   prefix[0] seen at index -1 and again at index 2
                   → subarray [0..2] = [3, 4, -7] sums to 0

                   prefix[0] seen again at index 5
                   → subarray [0..5] = [3, 4, -7, 1, 2, -3] sums to 0  ← longest!

Why initialise prefix = {0: -1}?

If the prefix sum reaches 0 at index i, it means nums[0..i] sums to zero. By storing 0 → -1 upfront, the length calculation i - prefix[0] = i - (-1) = i + 1 correctly gives the full subarray from index 0 to i.

---

Tracing the example

nums = [3, 4, -7, 1, 2, -3]

i	x	total	In prefix?	Action	best
-	-	0	-	Init prefix={0:-1}	len=0
0	3	3	No	prefix[3]=0	len=0
1	4	7	No	prefix[7]=1	len=0
2	-7	0	✅ at -1	len=2-(-1)=3, start=0	len=3
3	1	1	No	prefix[1]=3	len=3
4	2	3	✅ at 0	len=4-0=4, start=1	len=4
5	-3	0	✅ at -1	len=5-(-1)=6, start=0	len=6

Result: nums[0:6] = [3, 4, -7, 1, 2, -3]

---

Solution approaches

Pythonic (prefix sum hash map)Brute force (O(n²))Using lambda + enumerate

def largest_zero_sum_subarray(nums: list) -> list:
    prefix = {0: -1}
    total  = 0
    best_start, best_len = 0, 0

    for i, x in enumerate(nums):
        total += x
        if total in prefix:
            length = i - prefix[total]
            if length > best_len:
                best_len   = length
                best_start = prefix[total] + 1
        else:
            prefix[total] = i   # only store FIRST occurrence

    return nums[best_start : best_start + best_len]

def largest_zero_sum_subarray(nums: list) -> list:
    n = len(nums)
    best = []
    for i in range(n):
        total = 0
        for j in range(i, n):
            total += nums[j]
            if total == 0 and j - i + 1 > len(best):
                best = nums[i:j+1]
    return best

Simple to understand - check every subarray, keep the longest zero-sum one. O(n²) time, fine for small inputs.

def largest_zero_sum_subarray(nums: list) -> list:
    prefix = {0: -1}
    total  = 0
    candidates = []

    for i, x in enumerate(nums):
        total += x
        if total in prefix:
            candidates.append((i - prefix[total], prefix[total] + 1))
        else:
            prefix[total] = i

    if not candidates:
        return []
    best_len, best_start = max(candidates, key=lambda c: c[0])
    return nums[best_start : best_start + best_len]

Collect all zero-sum subarray (length, start) pairs, then use max(key=lambda c: c[0]) to find the longest. The lambda selects by length; first occurrence wins because max returns the first maximum.

---

Key takeaways

01

Prefix sum trick - same sum twice means zero in between

If prefix_sum[i] == prefix_sum[j] (i < j), then nums[i+1..j] sums to zero. Storing the first occurrence in a dict lets you find this in O(1) per element.

02

Initialise prefix = {0: -1}

This handles the case where the prefix sum itself reaches zero - meaning the entire subarray from index 0 is zero-sum. Without this sentinel, you'd miss subarrays starting at index 0.

03

Only store the first occurrence

When a prefix sum is already in the map, don't overwrite it. You want the earliest occurrence to maximise the subarray length. The else branch ensures this.