Introduction

Example – A = [1, 4 , -1, 3, -7,-3, -1,10]

Output – Yes

Subarrays with 0 sum – [1,-1] , [4,3,-7], [3,-3] , [-3,-7,10]

Approach

O(n) – Easily solvable in linear time with hashing. We traverse the given array, and maintain sum of elements seen so far in a hash map or dictionary . If sum is seen before (i.e. sum exists in dictionary/hash), we return true as there exists at-least one sub-array with zero sum which ends at current index else we insert the sum into the set.

Video Demonstration

Run Time Complexities

Time – O(n)

Space – O(n)

Code

C++

#include <iostream>
#include <unordered_set>
using namespace std;
 
// Function to check if subarray with zero-sum is present in a given array or not
bool hasZeroSumSubarray(int A[], int n)
{
    // create an empty set to store the sum of elements of each
    // subarray `A[0…i]`, where `0 <= i < n`
    unordered_set<int> set;
 
    // insert 0 into the set to handle the case when subarray with
    // zero-sum starts from index 0
    set.insert(0);
 
    int sum = 0;
 
    // traverse the given array
    for (int i = 0; i < n; i++)
    {
        // sum of elements so far
        sum += A[i];
 
        // if the sum is seen before, we have found a subarray with zero-sum
        if (set.find(sum) != set.end()) {
            return true;
        } else {
            // insert sum so far into the set
            set.insert(sum);
        }
    }
 
    // we reach here when no subarray with zero-sum exists
    return false;
}
 
int main()
{
    int A[] = { 4, 2, -3, -1, 0, 4 };
    int n = sizeof(A)/sizeof(A[0]);
 
    hasZeroSumSubarray(A, n) ?
            cout << "Subarray exists":
            cout << "Subarray does not exist";
 
    return 0;
}

Java

import java.util.Set;
import java.util.HashSet;
 
class Main
{
    // Function to check if subarray with zero-sum is present in a given array or not
    public static Boolean hasZeroSumSubarray(int[] A)
    {
        // create an empty set to store the sum of elements of each
        // subarray `A[0…i]`, where `0 <= i < arr.length`
        Set<Integer> set = new HashSet<>();
 
        // insert 0 into the set to handle the case when subarray with
        // zero-sum starts from index 0
        set.add(0);
 
        int sum = 0;
 
        // traverse the given array
        for (int value: A) {
            // sum of elements so far
            sum += value;
 
            // if the sum is seen before, we have found a subarray with zero-sum
            if (set.contains(sum)) {
                return true;
            }
 
            // insert sum so far into the set
            set.add(sum);
        }
 
        // we reach here when no subarray with zero-sum exists
        return false;
    }
 
    public static void main (String[] args)
    {
        int[] A = { 4, -6, 3, -1, 4, 2, 7 };
 
        if (hasZeroSumSubarray(A)) {
            System.out.println("Subarray exists");
        } else {
            System.out.println("Subarray does not exist");
        }
    }
}

Python

# Function to check if a sublist with zero-sum is present in a given list or not
def hasZeroSumSublist(A):
 
    # create an empty set to store the sum of elements of each
    # sublist `A[0…i]`, where `0 <= i < len(A)`
    s = set()
 
    # insert 0 into the set to handle the case when sublist with
    # zero-sum starts from index 0
    s.add(0)
 
    sum = 0
 
    # traverse the given list
    for i in A:
 
        # sum of elements so far
        sum += i
 
        # if the sum is seen before, we have found a sublist with zero-sum
        if sum in s:
            return True
 
        # insert sum so far into the set
        s.add(sum)
 
    # we reach here when no sublist with zero-sum exists
    return False
 
 
if __name__ == '__main__':
 
    A = [4, -6, 3, -1, 4, 2, 7]
 
    if hasZeroSumSublist(A):
        print("Sublist exists")
    else:
        print("Sublist does not exist")
 

You can use our online compiler to type and compile your code.

Review Please!
User Rating: 5.0 (1 votes)
Sending

LEAVE A REPLY

Rating