Tisha Agarwal

Posted on

# Subarray with 0 sum

Given an array of positive and negative numbers. Find if there is a subarray (of size at-least one) with 0 sum.

Example 1:
Input:
5
4 2 -3 1 6
Output:
Yes
Explanation:
2, -3, 1 is the subarray
with sum 0.

This is similar to the previous question Subarray sum equals k but this is EASY compared to that.

Approach 1:
Time Complexity: O(n^2)

JAVA CODE

``````public static boolean subArrayExists(int arr[],int n)
{
for(int i=0;i<n;i++)
{
int sum=0;
for(int j=i;j<n;j++)
{
sum+=arr[j];
if(sum==0)
return true;

}
}
return false;
}
``````

Approach 2:
This is similar to the previous subarray question that we solved.
Time Complexity: O(n)

JAVA CODE

``````  static boolean findsum(int arr[],int n)
{
HashMap<Integer,Integer> hm=new HashMap<>();
hm.put(0,1); // it is imp to put 0 initially in the hashmap
int sum=0;
for(int i=0;i<n;i++)
{
sum+=arr[i];
if(hm.containsKey(sum))
return true;

hm.put(sum,hm.getOrDefault(sum,0)+1);
}
return false;
}
``````

Approach 3:
We have used HashSet in this as their is no need to use HashMap since we have no use of storing values in key, pair
Time Complexity: O(n)

JAVA CODE

``````public static boolean subArrayExists(int arr[],int n)
{
//declare a set data structure
HashSet<Integer> res=new HashSet<>();
int sum=0;

for(int i=0;i<n;i++)
{
res.add(sum);//in first step it will add 0
sum+=arr[i];
if(res.contains(sum))
return true;
}
return false;

}
``````