What is the brute force approach and complexity for Subarray with 0 Sum?

Fix each start, grow the end with a running sum, stop at sum 0 with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Subarray with 0 Sum?

A zero-sum subarray exists iff some running total repeats (seed the set with 0) with optimal time complexity O(N) and space complexity O(N).

How do you identify the pattern for Subarray with 0 Sum?

Look for key signals in the prompt: "contiguous subarray" indicates A range [l..r] → its sum is a difference of two prefix sums.; "sum equals exactly 0" indicates Exact target → look up a prefix value, not a window bound.; "numbers can be negative" indicates A sliding window cannot decide when to shrink → use prefix sums.; "does one exist? (true/false)" indicates We only need to know if a prefix was seen → a hash set is enough, no counts..

Subarray with 0 Sum

Easy·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelPrefix Sum + Hash Set (repeated prefix)

Complexity:O(N²)→O(N)

Key Insight

Keep a running total prefix. A block arr[l..r] sums to 0 exactly when the total before l equals the total after r. So walk once, store every total in a hash set, and return true the first time a total shows up again. Put 0 in the set at the start for blocks that begin at index 0.

Core Validity Invariant

A zero-sum subarray ends at index i exactly when the current prefix is already in seen — the same total appeared earlier, so everything added since then sums to 0.

Problem

You are given an array of integers arr. The numbers can be positive, negative or zero.

Is there at least one contiguous, non-empty subarray whose elements add up to exactly 0?

Write bool subArrayExists(vector<int>& arr) that returns true if such a subarray exists and false otherwise.

Input

An integer array arr of length n. Values may be negative.

Output

true if some non-empty contiguous subarray has sum 0, otherwise false.

Example 1

Input: arr = [4, 2, -3, 1, 6]

Output: true

The subarray [2, -3, 1] (indices 1..3) adds up to 0.

Example 2

Input: arr = [4, 2, 0, 1, 6]

Output: true

The single element [0] is a subarray with sum 0.

Example 3

Input: arr = [-3, 2, 3, 1, 6]

Output: false

No contiguous block of these numbers adds up to 0.

Constraints

• 1 ≤ n ≤ 10^4
• −10^5 ≤ arr[i] ≤ 10^5

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
How many subarrays does an array of length n have? Could I check them all?
2.
If I keep a running total while walking from left to right, what does the total do across a block that sums to 0?
3.
If the running total has the same value at two different moments, what do the numbers in between add up to?
4.
Can a sliding window decide when to shrink if numbers can be negative?
5.
What about a zero-sum block that starts at the very first element?

Brute force approach

Idea

For every start, walk the end to the right and keep a running sum of arr[start..end]. If the sum is ever 0, we are done. If no start works, the answer is false.

Thinking process

1
A subarray is fixed by where it starts and where it ends. Try every pair.
2
Don't re-add the whole subarray for each pair: for one start, add one more element each time the end moves.
3
Unlike problems with only positive numbers, we cannot stop early when the sum gets big — a negative number later can bring it back to 0.
4
So for each start we walk all the way to the end of the array.

Code & Implementation

brute.cpp

class Solution {
public:
    bool subArrayExists(vector<int>& arr) {
        int n = arr.size();

        // Try every start, then grow the end one step at a time.
        for (int start = 0; start < n; start++) {
            long long sum = 0;
            for (int end = start; end < n; end++) {
                sum += arr[end];            // sum of arr[start..end]
                if (sum == 0) return true;
            }
        }
        return false;
    }
};

class Solution {
    public boolean subArrayExists(int[] arr) {
        int n = arr.length;

        // Try every start, then grow the end one step at a time.
        for (int start = 0; start < n; start++) {
            long sum = 0;
            for (int end = start; end < n; end++) {
                sum += arr[end]; // sum of arr[start..end]
                if (sum == 0) return true;
            }
        }
        return false;
    }
}

class Solution:
    def subArrayExists(self, arr: list[int]) -> bool:
        n = len(arr)

        # Try every start, then grow the end one step at a time.
        for start in range(n):
            current_sum = 0
            for end in range(start, n):
                current_sum += arr[end]
                if current_sum == 0:
                    return True
        return False

export function subArrayExists(arr: number[]): boolean {
    const n = arr.length;

    // Try every start, then grow the end one step at a time.
    for (let start = 0; start < n; start++) {
        let sum = 0;
        for (let end = start; end < n; end++) {
            sum += arr[end];
            if (sum === 0) return true;
        }
    }
    return false;
}

Complexity

Time O(N²)Space O(1)

About n²/2 (start, end) pairs. With n = 10^4 that is 5·10^7 steps — it may pass here, but it does not scale, and the next questions in this sub-pattern have much larger n.

Optimized approach

Idea

Start from brute force

Brute force builds the sum of arr[start..end] for every pair, starting a fresh running sum for each start.

Find the repeated work

Every start recomputes sums that are just differences of the same running totals. The running total from index 0 already holds everything: sum(l..r) = prefix[r+1] − prefix[l]. We only need to know whether two of those totals are equal.

Define the state — what variables do I need?

prefix: Sum of every element read so far (arr[0..i]).
seen: A hash set of every running total so far, including the starting total 0.

Define validity

A zero-sum subarray ends at index i exactly when the current prefix is already in seen — the same total appeared earlier, so everything added since then sums to 0.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

seen = {0}

0 is the total before reading anything. With it in the set, a block arr[0..i] that sums to 0 is found too.

Each element

prefix += arr[i]

Keep the running total up to date.

prefix is in seen

return true

If the total was p after some index j−1 and is p again after i, then arr[j..i] adds p − p = 0.

prefix is new

seen.insert(prefix)

A later index might come back to this same total, so remember it.

What does the current window add to the answer?

Each index asks one question: "has the running total been here before?" The first yes is the answer. If we reach the end with no repeat, every pair of totals is different, so no subarray sums to 0.

Code & Implementation

optimal.cpp

class Solution {
public:
    bool subArrayExists(vector<int>& arr) {
        // Every prefix sum we have seen so far.
        unordered_set<long long> seen;
        seen.insert(0);           // the empty prefix, so subarrays starting at index 0 count

        long long prefix = 0;
        for (int x : arr) {
            prefix += x;
            // Same total as before => everything added since then sums to 0.
            if (seen.count(prefix)) return true;
            seen.insert(prefix);
        }
        return false;
    }
};

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean subArrayExists(int[] arr) {
        // Every prefix sum we have seen so far.
        Set<Long> seen = new HashSet<>();
        seen.add(0L); // the empty prefix, so subarrays starting at index 0 count

        long prefix = 0;
        for (int x : arr) {
            prefix += x;
            // Same total as before => everything added since then sums to 0.
            if (seen.contains(prefix)) return true;
            seen.add(prefix);
        }
        return false;
    }
}

class Solution:
    def subArrayExists(self, arr: list[int]) -> bool:
        # Every prefix sum we have seen so far.
        seen = {0}  # empty prefix

        prefix = 0
        for x in arr:
            prefix += x
            # Same total as before => everything added since then sums to 0.
            if prefix in seen:
                return True
            seen.add(prefix)
        return False

export function subArrayExists(arr: number[]): boolean {
    // Every prefix sum we have seen so far.
    const seen = new Set<number>();
    seen.add(0); // empty prefix

    let prefix = 0;
    for (const x of arr) {
        prefix += x;
        // Same total as before => everything added since then sums to 0.
        if (seen.has(prefix)) return true;
        seen.add(prefix);
    }
    return false;
}

Complexity

Time O(N)Space O(N)

One pass with O(1) average set operations. The set can hold up to n + 1 totals.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Fix each start, grow the end with a running sum, stop at sum 0	O(N²)	O(1)
Optimal	A zero-sum subarray exists iff some running total repeats (seed the set with 0)	O(N)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“contiguous subarray”A range [l..r] → its sum is a difference of two prefix sums.
“sum equals exactly 0”Exact target → look up a prefix value, not a window bound.
“numbers can be negative”A sliding window cannot decide when to shrink → use prefix sums.
“does one exist? (true/false)”We only need to know if a prefix was seen → a hash set is enough, no counts.

Contiguous range+sum exactly 0+negatives allowed+yes/no answer→Prefix Sum + Hash Set (repeated prefix)

This is the anchor of the Exact sum + hash map sub-pattern. The key move: "some range sums to K" becomes "some earlier prefix equals prefix − K". Here K = 0, so we look for a prefix equal to the current one, and since we only need yes/no, a set is enough. The next question (count zero-sum subarrays) keeps the same idea but needs a map of counts, and Subarray Sum Equals K then changes the lookup key to prefix − k.

Don't make this mistake

Using a sliding window

✗ sum += arr[r]; while (sum > 0 && l <= r) sum -= arr[l++]; if (sum == 0 && l <= r) return true;

✓ if (seen.count(prefix)) return true; seen.insert(prefix);

This is a pattern-confusion trap. A window drops the left element when the sum is "too big", which assumes the sum can only grow as the window grows. With negatives that is false. On [2, -1, -1] the window drops the 2 right away (sum 2 > 0), then never sees 2 − 1 − 1 = 0, and returns false.

Forgetting to put 0 in the set first

✗ unordered_set<long long> seen; // empty

✓ unordered_set<long long> seen; seen.insert(0);

A zero-sum block that starts at index 0 means the running total itself becomes 0. Without the starting 0 in the set there is nothing to match. [-3, 3, 5] has totals -3, 0, 5 — all different — so the code wrongly returns false.

Inserting before checking

✗ seen.insert(prefix); if (seen.count(prefix)) return true;

✓ if (seen.count(prefix)) return true; seen.insert(prefix);

The check is always true after inserting, so the code returns true on the first element. We must compare with earlier totals only.

Thinking you need the subarray's exact position

The question only asks yes/no, so a set is enough. If you later need the subarray itself (or the longest one), store prefix → first index in a map instead.

Want to implement this?

Write it yourself on GeeksforGeeks, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Prefix Sum translate into production architectures and low-level memory mechanics.

LLD Architecture