Check if a subarray with 0 sum exists or not

Problem Statement

Let us say that we have given an array arr. We need to check if any subarray of the array arr has a sum value of 0. If it does, then it should print the statement " Subarray with zero-sum exists ". On the other hand, if there is no subarray with sum 0, then it must print the statement " Subarray with zero-sum does not exists " .

Example:

Sample test 1

arr = [1,2,-3, 4, 7,-6, -10]
Output: Subarray with zero-sum exists

Explanation In the above array arr , there are some subarrays, with each subarray having a sum equal to 0.

[1,2,-3]
[4,2,-6]
[3,7,-10]

As you can see, the sum of each subarray is 0.

Sample test 2

arr = [1,2,3,4,-12,-13]

Output: 

Subarray with zero-sum does not exists

Explanation In the above array, there is no such subarray that has a sum equal to 0. And that's why it prints the statement Subarray with zero-sum does not exists .

Solution

To solve the problem we can use the set hashing technique, which is explained as follows:

• Using the set hashing, we will first create an empty set s that contains only unique elements in the given array.
• Insert 0 in the set s .
• Now, we will traverse through every element of the array arr and keep adding the array elements with each iteration. Also, we will store the resulting value in the variable sum .
• In each iteration, we will check if the value of sum already exists in the set s.
• If yes, we will return 'True' and print the statement Subarray with zero-sum exists.
• If the loop gets completed  and no value of sum is in the array, we will return 'False' and print the statement Subarray with zero-sum does not exists.

The basic idea is that if the prefix sum of the array is already present in the set s , it means the array contains a subarray that has a sum equal to zero.

Example

The prefix sum of the array [1,2,-3, 4, 7,-6, -10] is [1,3,0,4,11,5,-5] . In this prefix sum, we are getting an element 0 which already exists in the set s . Not only zero, but if two common prefix sum comes in an array, this means the array contains a zero-sum subarray. The two common prefix sum indicates that the sum of the elements between those prefix sum is zero.

C++ Code to Check if a Subarray with 0 Sum Exists or Not

#include <iostream>
#include <set>
using namespace std;
 
// boolean Function to check if subarray with zero-sum is present in a given array or not
bool hasSumZeroSubarray(int arr[], int n)
{
    // create an empty set s that will store the prefix sum of array elements
    set <int> s;
 
    // insert 0 into set s
    s.insert(0);
 	
 	//elements prefix sum
    int sum = 0;
 
    // traverse the given array
    for (int i = 0; i < n; i++)
    {
        // add the elements
        sum += arr[i];
 
        // check if sum is already present in the set s
        if (s.count(sum)) {
            return true;
        }
        else {
            // insert the sum into set if sum is not present in the set
            s.insert(sum);
        }
    }
 
    // if there is no subarray with sum 0
    return false;
}
 
int main()
{	//given array
    int arr[] = {1,2,-3, 4, 7,-6, -10};
    
    //size of the array
    int n = sizeof(arr)/sizeof(arr[0]);
 
    if(hasSumZeroSubarray(arr, n))
    {
    	cout << "Subarray with zero-sum exists";
	}
	else
	{
		cout << "Subarray with zero-sum does not exists";
	}            
            
    return 0;
}

Output

Python Code to Check if a Subarray with 0 Sum Exists or Not

def hasSumZeroSubarray(arr, n):
    #create an empty set s
    s= set()

    #insert 0 as the first element into set s
    s.add(0)

    #initializing variable sum_ that will store the sum of array elements
    sum_= 0

    #traverse through array elements
    for element in arr:
        
        #add the array elements 
        sum_+=element

        #check if the sum_ present in the set s
        if sum_ in s:
            return True

        # add sum in the set s
        else:
            s.add(sum_)

    return False

if __name__ =="__main__":
    #given array
    arr= [1,2,-3, 4, 7,-6, -10]
    
    #size of the array
    n = len(arr)

    if hasSumZeroSubarray(arr,n):
        print("Subarray with zero-sum exists")
    else:
        print("Subarray with zero-sum does not exists")

Output

Complexity

• Time Complexity: O(N) : The time complexity of the above programs is O(N), where N is the total number of elements present in the array. The time complexity is linear because we are going through the array list only once.
• Space Complexity: O(N): The space complexity of the above algorithms is also O(N) because we are using a set that can also have N number of elements.

Conclusion

To check if a subarray with 0 sum exists or not is one of the most common programming problems. In this tutorial, we have only covered the set hashing technique to check if an array contains any subarray with sum zero that leads to the time complexity of O(N).

You can also use the brute force or naive approach where you have to find out all the subarrays of an array and check if any of the subarrays has a sum equal to zero. The time complexity of that algorithm would be O(N^N).

People are also reading:

• Rearrange an array such that arr[i] = i
• Minimum Edit Distance
• The Stock Span Problem
• WAP to Print Triangle Using * Character
• Find ancestors of a given node in a Binary Tree
• Subset Sum Problem
• Clone a Singly Linked List
• Maximum size square sub-matrices with all 1’s
• Merge Sort for Linked Lists
• How to find and remove loops in a Linked List?