Subarray with Sum Zero

Last Updated : 3 Apr, 2026

Given an array arr[] containing both positive and negative integers, check whether there exists a non-empty subarray whose sum is equal to zero.

Examples:

Input: arr[] = [4, 2, -3, 1, 6]
Output: true
Explanation: There is a subarray with zero sum from index 1 to 3 .Sum of subarray [2,-3,1] is 0 .

Input: arr[]=[4, 2, 0, 1, 6]
Output: true
Explanation: The third element is zero. A single element is also a sub-array.
Input: arr[]=[-3, 2, 3, 1, 6]
Output: false

Try it on GfG Practice

Table of Content

[Naive Approach] Using Nested Loop - O(n^2) Time and O(1) Space
[Expected Approach] Using Hashing - O(n) Time and O(n) Space

[Naive Approach] Using Nested Loop - O(n^2) Time and O(1) Space

Generate every subarray using two nested loops and calculate the sum of each subarray. Check if subarray sum is 0 then return true. Otherwise, if no such subarray found then return false.

C++

#include <iostream>
#include <vector>
using namespace std;

bool subArrayExists(vector<int>& arr)
{
    for (int i = 0; i < arr.size(); i++) {
      
        // starting point of the sub arrray and
        // sum is initialized with first element of subarray
        // a[i]
        int sum = arr[i];
        if (sum == 0)
            return true;

        for (int j = i + 1; j < arr.size(); j++) {
          
            // we are finding the sum till jth index
            // starting from ith index
            sum += arr[j];
            if (sum == 0)
                return true;
        }
    }
    return false;
}

int main()
{
    vector<int> arr = { -3, 2, 3, 1, 6 };
    if (subArrayExists(arr))
        cout << "true";
    else
        cout << "false";

    return 0;
}

Java

import java.util.ArrayList;

public class Main {
    public static boolean subArrayExists(ArrayList<Integer> arr) {
        for (int i = 0; i < arr.size(); i++) {
            
            // starting point of the sub arrray and
            // sum is initialized with first element of subarray
            // a[i]
            int sum = arr.get(i);
            if (sum == 0)
                return true;
            for (int j = i + 1; j < arr.size(); j++) {
                
                // we are finding the sum till jth index
                // starting from ith index
                sum += arr.get(j);
                if (sum == 0)
                    return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        ArrayList<Integer> arr = new ArrayList<Integer>();
        arr.add(-3);
        arr.add(2);
        arr.add(3);
        arr.add(1);
        arr.add(6);
        if (subArrayExists(arr))
            System.out.println("true");
        else
            System.out.println("false");
    }
}

Python

def subArrayExists(arr):
    for i in range(len(arr)):
        
        # starting point of the sub arrray and
        # sum is initialized with first element of subarray
        # a[i]
        sum = arr[i]
        if sum == 0:
            return True
        for j in range(i + 1, len(arr)):
            
            # we are finding the sum till jth index
            # starting from ith index
            sum += arr[j]
            if sum == 0:
                return True
    return False

if __name__ == '__main__':
    arr = [-3, 2, 3, 1, 6]
    if subArrayExists(arr):
        print('true')
    else:
        print('false')

C#

using System;
using System.Collections.Generic;

class Program {
    static bool subArrayExists(List<int> arr) {
        for (int i = 0; i < arr.Count; i++) {
            
            // starting point of the sub arrray and
            // sum is initialized with first element of subarray
            // a[i]
            int sum = arr[i];
            if (sum == 0)
                return true;
            for (int j = i + 1; j < arr.Count; j++) {
                
                // we are finding the sum till jth index
                // starting from ith index
                sum += arr[j];
                if (sum == 0)
                    return true;
            }
        }
        return false;
    }

    static void Main() {
        List<int> arr = new List<int> { -3, 2, 3, 1, 6 };
        if (subArrayExists(arr))
            Console.WriteLine("true");
        else
            Console.WriteLine("false");
    }
}

JavaScript

function subArrayExists(arr) {
    for (let i = 0; i < arr.length; i++) {
        
        // starting point of the sub arrray and
        // sum is initialized with first element of subarray
        // a[i]
        let sum = arr[i];
        if (sum === 0)
            return true;
        for (let j = i + 1; j < arr.length; j++) {
            
            // we are finding the sum till jth index
            // starting from ith index
            sum += arr[j];
            if (sum === 0)
                return true;
        }
    }
    return false;
}

let arr = [-3, 2, 3, 1, 6];
if (subArrayExists(arr))
    console.log('true');
else
    console.log('false');

Output

false

[Expected Approach] Using Hashing - O(n) Time and O(n) Space

The idea is to iterate through the array and for every element arr[i], calculate the sum of elements from 0 to i (this can simply be done as sum += arr[i]). If the current sum has been seen before, then there must be a zero-sum subarray. Hashing is used to store the sum values so that sum can be stored quickly and find out whether the current sum is seen before or not.

arr[] = {1, 4, -2, -2, 5, -4, 3}
Consider all prefix sums, one can notice that there is a subarray with 0 sum when :
Either a prefix sum repeats
Or, prefix sum becomes 0.
Prefix sums for above array are: 1, 5, 3, 1, 6, 2, 5
Since prefix sum 1 repeats, we have a subarray with 0 sum.
Corner Case : The whole prefix can also be 0, so along with repetition of prefix sum, we also need to check if prefix sum becomes 0.

C++

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

bool subArrayExists(vector<int>& arr)
{
    unordered_set<int> sumSet;

    // Traverse through array
    // and track prefix sums
    int sum = 0;
    for (int i = 0; i < arr.size(); i++) {
        sum += arr[i];

        // If prefix sum is 0 or it is already present
        if (sum == 0 || sumSet.find(sum) != sumSet.end())
            return true;

        sumSet.insert(sum);
    }
    return false;
}

int main()
{
    vector<int> arr = {-3, 2, 3, 1, 6};

    if (subArrayExists(arr))
        cout << "true";
    else
        cout << "false";

    return 0;
}

Java

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

public class Main {
    public static boolean subArrayExists(int[] arr) {
        Set<Integer> sumSet = new HashSet<>();

        // Traverse through array
        // and track prefix sums
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];

            // If prefix sum is 0 or it is already present
            if (sum == 0 || sumSet.contains(sum))
                return true;

            sumSet.add(sum);
        }
        return false;
    }

    public static void main(String[] args) {
        int[] arr = {-3, 2, 3, 1, 6};

        if (subArrayExists(arr))
            System.out.println("true");
        else
            System.out.println("false");
    }
}

Python

def subArrayExists(arr):
    sumSet = set()

    # Traverse through array
    # and track prefix sums
    sum = 0
    for i in range(len(arr)):
        sum += arr[i]

        # If prefix sum is 0 or it is already present
        if sum == 0 or sum in sumSet:
            return True

        sumSet.add(sum)
    return False

if __name__ == '__main__':
    arr = [-3, 2, 3, 1, 6]

    if subArrayExists(arr):
        print('true')
    else:
        print('false')

C#

using System;
using System.Collections.Generic;

public class Program
{
    public static bool subArrayExists(int[] arr)
    {
        HashSet<int> sumSet = new HashSet<int>();

        // Traverse through array
        // and track prefix sums
        int sum = 0;
        for (int i = 0; i < arr.Length; i++)
        {
            sum += arr[i];

            // If prefix sum is 0 or it is already present
            if (sum == 0 || sumSet.Contains(sum))
                return true;

            sumSet.Add(sum);
        }
        return false;
    }

    public static void Main()
    {
        int[] arr = { -3, 2, 3, 1, 6 };

        if (subArrayExists(arr))
            Console.WriteLine("true");
        else
            Console.WriteLine("false");
    }
}

JavaScript

function subArrayExists(arr) {
    let sumSet = new Set();

    // Traverse through array
    // and track prefix sums
    let sum = 0;
    for (let i = 0; i < arr.length; i++) {
        sum += arr[i];

        // If prefix sum is 0 or it is already present
        if (sum === 0 || sumSet.has(sum))
            return true;

        sumSet.add(sum);
    }
    return false;
}

let arr = [-3, 2, 3, 1, 6];

if (subArrayExists(arr))
    console.log('true');
else
    console.log('false');

Output

false

Comment

Article Tags:

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem