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.

Example 2:

Input:
5
4 2 0 1 6

Output: 
Yes

Explanation: 
0 is one of the element 
in the array so there exist a 
subarray with sum 0.



method 1 : hashing:

1) 
Iterate through the array and for every element a[i], calculate prefix sum.
2)If we consider all prefix sums, we can notice that there is a subarray with 0 sum when either a prefix sum repeats or prefix sum becomes 0.
3)In both cases, we return true else we store the prefix sum in map and keep iterating.
4)Return false if you don't get any subarray with 0 sum.



c++ implementation:

 bool subArrayExists(int arr[], int n)
 {
   map <int,int> mp;
   int sum=0;
   for(int i=0;i<n;i++)
   {
       sum=sum+arr[i];
       if(sum==0 || mp.count(sum)==1)
         return 1;
       else
         mp[sum]=1;
   }
   return 0;
 }


Time Complexity: O(n) 
space Complexity: O(n) 



darkmode