Log inSign up
mediumGeeksforGeeksNot Started

Longest Subarray with Sum Zero

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an array arr of n integers containing both positive and negative numbers, find the length of the longest subarray with a sum equal to 0.

If no such subarray exists, return 0.

Example 1 · Standard Array with Multiple Zero-Sum Subarrays:

Input: arr = [15, -2, 2, -8, 1, 7, 10, 23]
Output: 5
Explanation: The longest sub-array with sum 0 is [-2, 2, -8, 1, 7] starting from index 1 to 5 (length 5).

Example 2 · Prefix Sum Equal to Zero from Origin:

Input: arr = [2, -2, 3, -3]
Output: 4
Explanation: The entire array [2, -2, 3, -3] has sum 0, length is 4.

Example 3 · No Zero Sum Subarray:

Input: arr = [1, 2, 3]
Output: 0
Explanation: All subarray sums are positive. No zero sum subarray exists.

Constraints:

  • 1 <= arr.length <= 105
  • -104 <= arr[i] <= 104

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Prefix sum array concept
  • Hash Map (dictionary) key lookup and storage

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master prefix sum identity for zero-sum subarrays.
  • Understand why storing only the first occurrence maximizes subarray length.
  • Distinguish when hash maps are needed over two-pointer sliding windows (presence of negative numbers).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If the array is sorted or can be sorted without violating problem requirements, evaluate Two Pointers or Binary Search.
  • If tracking contiguous subsegments with monotone expansion/shrinkage, apply Sliding Window.
  • If frequency or complement lookups are required in O(1) time, use a Hash Map or Frequency Array.

Connected Patterns:

Subarray Sum Equals KContinuous Subarray SumSubarray Sums Divisible by K

1. Check All Subarrays (Brute Force)

Intuition

Iterate with two nested loops: start from 0 to n-1, end from start to n-1. Accumulate elements in currentSum. If currentSum == 0, maxLen = max(maxLen, end - start + 1).

When to apply: Use to understand the baseline search for zero-sum windows.

Brute Force Zero-Sum Subarray Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [15, -2, 2, -8, 1, 7, 10, 23]
Current operationSTEP 1 OF 6
Array: [15, -2, 2, -8, 1, 7, 10, 23]
Visual state
Values and pointers at this exact step
pointers
S
15
-2
2
-8
1
7
10
23
0
↑ Start
1
2
3
4
5
6
7
Variables at this step
start
0
maxLen
0
Check / comparison
Start at index 0.
Decision / next transition
Begin subarray searches.
Why this step matters

Array: [15, -2, 2, -8, 1, 7, 10, 23]. Initialize maxLen = 0. start = 0.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int maxLen(int[] arr) {
4 int maxLen = 0;
5 for (int i = 0; i < arr.length; i++) {
6 int sum = 0;
7 for (int j = i; j < arr.length; j++) {
8 sum += arr[j];
9 if (sum == 0) {
10 maxLen = Math.max(maxLen, j - i + 1);
11 }
12 }
13 }
14 return maxLen;
15 }
16 }
17
18 public static void main(String[] args) {
19 Solution sol = new Solution();
20 int[] arr = {15, -2, 2, -8, 1, 7, 10, 23};
21 System.out.println("Max length: " + sol.maxLen(arr));
22 }
23}

Time & Space Complexity

  • Time complexity: O(n^2) — Nested loops test all n*(n+1)/2 subarrays.
  • Space complexity: O(1) — Only scalar max length tracker is maintained.

Why Brute Force Doesn't Scale:

For N = 100,000, N2 requires 10 billion operations.

Prefix sum hash map does 1 single pass with 100,000 lookups, completing in milliseconds.

2. Prefix Sum Array with Pair Difference Search

Intuition

Compute prefix array where prefix[k] is the sum of the first k elements. A subarray arr[i..j-1] has sum zero if and only if prefix[j] == prefix[i].

When to apply: Use to understand prefix sum identity for zero-sum subarrays.

Prefix Equality Search Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [15, -2, 2, -8, 1, 7, 10, 23]
Current operationSTEP 1 OF 6
Prefix array: [0, 15, 13, 15, 7, 8, 15, 25, 48]
Visual state
Values and pointers at this exact step
pointers
S
15
-2
2
-8
1
7
10
23
0
↑ Sum=15
1
2
3
4
5
6
7
Variables at this step
prefix15_indices
[1,3,6]
Check / comparison
prefix[1] == 15, prefix[3] == 15, prefix[6] == 15.
Decision / next transition
Pairs sharing prefix sum 15 define zero-sum subarrays.
Why this step matters

Prefix array: [0, 15, 13, 15, 7, 8, 15, 25, 48]. Notice prefix sum 15 appears at indices 1, 3, and 6.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int maxLen(int[] arr) {
4 int n = arr.length;
5 int[] prefix = new int[n + 1];
6 for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + arr[i];
7
8 int maxLen = 0;
9 for (int i = 0; i <= n; i++) {
10 for (int j = i + 1; j <= n; j++) {
11 if (prefix[j] == prefix[i]) {
12 maxLen = Math.max(maxLen, j - i);
13 }
14 }
15 }
16 return maxLen;
17 }
18 }
19
20 public static void main(String[] args) {
21 Solution sol = new Solution();
22 int[] arr = {15, -2, 2, -8, 1, 7, 10, 23};
23 System.out.println("Max length: " + sol.maxLen(arr));
24 }
25}

Time & Space Complexity

  • Time complexity: O(n^2) — O(n) to compute prefix sums, O(n2) to search pairs.
  • Space complexity: O(n) — O(n) auxiliary prefix sum array.

3. Prefix Sum + First Occurrence Hash Map (Optimal & Standard)

Intuition

1. Maintain running prefix sum and hash map mapping prefixSum -> earliest index. 2. If prefixSum == 0, maxLen = i + 1. 3. If prefixSum is already in map, candidate length is i - map.get(prefixSum); update maxLen. 4. Only store prefixSum the first time it appears to maximize subarray length.

When to apply: Use as the optimal standard for any longest subarray with target sum.

Earliest Prefix Index Hash Map Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [15, -2, 2, -8, 1, 7, 10, 23]
Current operationSTEP 1 OF 6
i=0: num=15
Visual state
Values and pointers at this exact step
pointers
S
15
-2
2
-8
1
7
10
23
0
↑ i=0
1
2
3
4
5
6
7
Variables at this step
sum
15
map
{"15":0}
maxLen
0
Check / comparison
First time seeing sum 15.
Decision / next transition
map[15] = 0, maxLen = 0.
Why this step matters

i=0: num=15. sum = 15. Map does not have 15. Store map[15] = 0.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int maxLen(int[] arr) {
6 Map<Integer, Integer> map = new HashMap<>();
7 int maxLen = 0, sum = 0;
8
9 for (int i = 0; i < arr.length; i++) {
10 sum += arr[i];
11 if (sum == 0) {
12 maxLen = i + 1;
13 } else if (map.containsKey(sum)) {
14 maxLen = Math.max(maxLen, i - map.get(sum));
15 } else {
16 map.put(sum, i);
17 }
18 }
19 return maxLen;
20 }
21 }
22
23 public static void main(String[] args) {
24 Solution sol = new Solution();
25 int[] arr = {15, -2, 2, -8, 1, 7, 10, 23};
26 System.out.println("Max length: " + sol.maxLen(arr));
27 }
28}

Time & Space Complexity

  • Time complexity: O(n) — Single linear pass with O(1) hash map operations.
  • Space complexity: O(n) — Hash map stores up to n distinct prefix sums.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — All Subarrays O(N2)O(N^2)O(1)Generate all pairs (i, j). Calculate sum of subarray arr[i..j]. If sum == 0, update maxLen = max(maxLen, j - i + 1).Iterating through all O(N2) subarray pairs.
2.Better — Precomputed Prefix Sum ArrayO(N^2)O(N)Precompute prefix sum array. Then check all pairs (i, j) where prefix[j] - prefix[i-1] == 0 in O(1) per pair.Checking all index pairs.
3.Optimal — Prefix Sum + First Occurrence Hash MapOptimalO(N)O(N)Maintain running prefix sum. If prefix sum == 0, length is i + 1. Otherwise, if prefix sum is in map, update maxLen = max(maxLen, i - map.get(prefixSum)). If not in map, store map[prefixSum] = i.None; theoretical optimum.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Longest Subarray with Sum Zero?

2.Why is the brute force approach suboptimal for large inputs in Longest Subarray with Sum Zero?

3.Which data structure or technique enables the optimal solution for Longest Subarray with Sum Zero?

Back to DSA Sheet