Jun 26, 2025•

Print All Zero Sum Subarray

Designer & Developer

Table of Contents

1.🧠 Print All Zero-Sum Subarrays in an Array
2.✅ Problem Statement
3.🧩 Example
4.🔍 Approach 1: Brute-Force (O(n²))
5.🐍 Python Code
6.🔎 When to Use
7.⚡ Approach 2: Prefix Sum with HashMap (O(n))
8.💡 Idea
9.🐍 Python Code
10.🧪 Trace Example
11.📝 Summary

🧠 Print All Zero-Sum Subarrays in an Array

✅ Problem Statement

Given an array of integers, find and print all contiguous subarrays whose sum is zero.

🧩 Example

Input: [3, 4, -7, 3, 1, 3, 1, -4, -2, -2]
Output:
  Subarray found from Index 0 to 2
  Subarray found from Index 1 to 3
  Subarray found from Index 2 to 4
  Subarray found from Index 6 to 9
  ...and more

🔍 Approach 1: Brute-Force (O(n²))

For every starting index, try all possible subarrays
Keep a running sum
If at any point, the sum is zero → print the subarray's index range

🐍 Python Code

def print_all_zero_sum_sublists_brute(nums):
    for i in range(len(nums)):
        total = 0
        for j in range(i, len(nums)):
            total += nums[j]
            if total == 0:
                print(f"Subarray found from Index {i} to {j}")

🔎 When to Use

Simple to understand
Not suitable for large arrays

⚡ Approach 2: Prefix Sum with HashMap (O(n))

This method uses a prefix sum and a dictionary to track previous sums. If the same prefix sum appears again, it means the subarray in between sums to zero.

💡 Idea

Maintain a cumulative prefix_sum
Store all indices where a particular prefix_sum has occurred
If prefix_sum repeats, all subarrays between previous and current index are zero-sum

🐍 Python Code

def insert(d, key, value):
    d.setdefault(key, []).append(value)
 
def print_all_zero_sum_sublists(nums):
    d = {}
    insert(d, 0, -1)  # For subarrays starting from index 0
    total = 0
 
    for i in range(len(nums)):
        total += nums[i]
 
        if total in d:
            for start_index in d[total]:
                print(f"Subarray found from Index {start_index + 1} to {i}")
        insert(d, total, i)

🧪 Trace Example

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

Index	Value	Prefix Sum	Seen at Indices	New Subarrays
0	3	3	—	—
1	4	7	—	—
2	-7	0	[-1]	(0, 2)
3	3	3	[0]	(1, 3)
4	1	4	—	—
5	3	7	[1]	(2, 5)
6	1	8	—	—
7	-4	4	[4]	(5, 7)
8	-2	2	—	—
9	-2	0	[-1, 2]	(0, 9), (3, 9)

📝 Summary

Approach	Time	Space	Notes
Brute-force	O(n²)	O(1)	Easy to write, slow for large n
Prefix Hashing	O(n)	O(n)	Efficient and elegant

← Previous

find pair

Next →

automating my mdx blog workflow with a simple node js script