Subarray with 0 sum

Difficulty Level Medium
Frequently asked in Citrix DE Shaw Goldman Sachs Indeed MakeMyTrip OYO Rooms Paytm TCS
Array HashViews 5086

The problem “Find if there is a subarray with 0 sum” states that you are given an integer array containing negative integers as well. The problem statement asks to determine if any sub-array of size at-least 1. This sub-array should have a sum equal to 1.

Example

Find if there is a subarray with 0 sum

arr[] = {2,1,-3,4,5}
yes

Explanation

Here, elements from index 0 to 2 have a sum 0.

arr[] = {4,1,-4,5,1}
yes

Explanation

No sub-array exists that has sum 0.

Algorithm

  1. Declare a Set.
  2. Initialize sum to 0.
  3. Traverse the array, while i < n (length of the array).
    1. Add sum to arr[i] and store it to sum.
    2. Check if any of the following conditions is true:
      1. sum==0 / arr[ i ]==0 / if Set contains the value of sum.
      2. if true, then return true.
    3. Add the sum to the Set.
  4. Return false.

Explanation

We got a problem statement that asks to find out if there is any sub-array exists with a sum equal to 0. To solve this we will use a Set to solve this problem. We are going to store the elements of a given array into the Set. Then simultaneously add the value into the sum and check if there is any match of sub-array with the current sum in the set or the sum itself equals 0. If there is found to be a sub-array with sum 0 then we will return true.

If none of the sub-arrays found to have sum 0, then we are going to return false out of the loop. Also, there is one thing, if any of an element is 0 then also we will return true because an element itself is a sub-array of one single element. So it means we found one such sub-array.

Here in the code, we declare a Boolean function, it will return either true or false, if sub-array found, it returns true, else it will return false.

Let us consider an example:

Example

arr[]={-3,2,1,9,6}

Here in the code, we will be traversing an array and add sum and arr[i] and store into sum and after that checking, if sum ==0 or arr[i] is equal to 0 or Set contains the value of sum, if any of the given condition is satisfied then we are going to return true and then add sum into Set.

If none of the sub-array found then we will going to return false.

sum=0, Set={}

i=0, arr [i] = -3

sum = sum+arr[i] => 0 + – 3 = -3

if sum ==0 or arr[i] is equal to 0 or Set contains the value of sum, three of them are false, so we do nothing here and add -3 into Set.

i=1, arr [i] = 2

sum = sum+arr[i] => -3 + 2 = -1

if sum ==0 or arr[i] is equal to 0 or Set contains the value of sum, three of them are false, so we do nothing here and add -1 into Set.

i=2, arr [i] = 1

sum = sum+arr[i] => -1 + 1 = 0

if sum ==0 condition is satisfied here, so we return true, it means we found a sub-array with sum 0.

Output: Yes, a sub-array with sum 0 exists.

Code

C++ code to Find if there is a subarray with 0 sum

#include<iostream>
#include<unordered_set>

using namespace std;

bool isSubArrayZero(int arr[], int n)
{
    unordered_set<int> Set;
    int sum = 0;
    for (int i = 0 ; i < n ; i++)
    {
        sum += arr[i];
        if (sum == 0 || Set.find(sum) != Set.end())
            return true;

        Set.insert(sum);
    }
    return false;
}
int main()
{
    int arr[] = {-3, 2, 1, 9, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    if (isSubArrayZero(arr, n))
        cout << "Yes, a sub-array with sum 0 exist";
    else
        cout << "No, a sub-array with sum 0 does not exist";
    return 0;
}

Yes, a sub-array with sum 0 exist

Java code to Find if there is a subarray with 0 sum

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

class sumOfSubArrayZero
{
    public static Boolean isSubArrayZero(int arr[])
    {
        Set<Integer> set = new HashSet<Integer>();
        int Sum = 0;
        for (int i = 0; i < arr.length; i++)
        {
            Sum += arr[i];
            if (arr[i] == 0 || Sum == 0 || set.contains(Sum))
                return true;

            set.add(Sum);
        }
        return false;
    }
    public static void main(String arg[])
    {
        int arr[] = {-3, 2, 1, 9, 6};
        if (isSubArrayZero(arr))
            System.out.println("Yes, a subarray with sum 0 exists");
        else
            System.out.println("No, a subarray with sum 0 does not exist");
    }
}

Yes, a subarray with sum 0 exists

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. All of this was possible because of using a HashSet because it allows us to perform insert, search, delete in O(1) time.

Space Complexity

O(n) where “n” is the number of elements in the array. Since there can be at most n elements in the created hash set, the space complexity is linear.

Translate »