Largest Subarray with Sum 0

Medium

Two equal prefix sums bracket a zero-sum run

Problem

You are given an integer array arr of size n which contains both positive and negative integers. Your task is to find the length of the longest contiguous subarray with sum equal to 0. Return the length of such a subarray. If no such subarray exists, return 0.

In simple words

If the running sum repeats, the slice between the two spots adds to zero — track first sightings.

The idea

If the same prefix sum appears at two positions, everything between them sums to zero. Recording the first index at which each prefix sum occurs and measuring back to it gives the longest such stretch in one pass.

The trick

Store the earliest index per prefix sum; overwriting shortens the answer.
A prefix sum of 0 means the subarray starts at index 0.
O(n) time, O(n) space.

←→stepspaceplay

-3

-1

-5

target0

1/23

Brute force

timeO(n²)spaceO(1)

Every subarray.

1for (let i = 0; i < n; i++) {2  let sum = 0;3  for (let j = i; j < n; j++) {4    sum += nums[j];5    if (sum === 0) best = Math.max(best, j - i + 1);6  }7}

Input

array: [9, -3, 3, -1, 6, -5]

Memory

target: 0

Output

best length: —
answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: nums = [15, -2, 2, -8, 1, 7, 10, 23]
Output:: 5
Explanation:: [-2,2,-8,1,7] sums to 0 → length 5.

Example 2

Input:: nums = [1, -1, 3]
Output:: 2
Explanation:: [1,-1] cancels → length 2.

Example 3

Input:: nums = [1, 2, 3]
Output:: 0
Explanation:: No zero-sum stretch → 0.

Constraints

1 <= arr.length <= 10^6
-10^3 <= arr[i] <= 10^3 for each valid index i

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.