Question : You are give an array with integers , your task is to find the longest subarray within that array which sums equal to 0.
Input: arr[] = {15, -2, 2, -8, 1, 7, 10, 23}; Output: 5 Explanation: The longest sub-array with elements summing up to 0 is {-2, 2, -8, 1, 7}
Brute Solution:
We can perform the required task by generating all the subarrays. To do this , keep a pointer at the starting position of the array .Say pointer i is at arr[0] .Now arr[15]=0 .So we will be iterating from i+1 to n-1 (n=size of array) and going to take all the subarrays.Example :
1. i=0 , j=1 , subarray with 2 elements
2. i=0 , j=2 , subarray with 3 elements
.
.
.
a. i=2 , j=5 , subarray with 4 elements ,
.
.
.
z. i=n-2 , j=n-1 , subarry with 2 elements
hence we will be generating the subarrays like this and take the summation of all the elements in a subarray and check if it is 0 , if it equals to zero we will taking the length of subarray and return the longest one.
Pseudo Code:
for(i=0 to n-2){
sum=arr[i];
for(j=i+1 to n-1){
sum+=arr[j];
if(sum==0)len=max(len,j-i)
}
}
Time complexity=O(n^2)
Space complexity=O(1)
Optimal Solution :
The main idea behind this solution is , say we got 1 at 2nd position as a sum , now if we get 1 again at 7th position , so the subarry from 3rd position to 7th position sums equal to zero. becuase 1+0=1.
In order to implement this idea , we will keep a hashmap , and going to put our summation with index in the map , if we get a element same as the current sum in the map then the sumation from next of that element index to current index is zero.
We will start iterating from first position of array , and add the array element to a variable sum , now if we dont have the sum in the map , we are going to add this value to map , if we got a sum which is already there in
the map, we found a candidate for our answer ,and if we got our sum as 0 then we will take the length for this subarray from starting to current position .
Example :
input array : 15, -2, 2, -8, 1, 7, 10, 23
sum : 15,13,15,7,8,15,25,48
Here you can see first time sum is repeated in 2nd position , so length of subarray which gives 0 sum , =(2-0)=2 , 1st index and 2nd index gives us 0 sum , so our current lenght is =2 , similarly , we got repeation in 5th position , now our length becomes 5. so this is our answer , because no other subarry is giving 0 till end of the array.
Code :
C++
Function to return the length of longest subarry with 0 sum:
int calculate(vector<int>&A,int n){
map<int,int>m;
int sum=0;
int res=0;
for(int i=0;i<n;i++)
{
sum+=A[i];
if(sum==0)
{
res=max(res,i+1);}
if(m.find(sum)!=m.end())
{
int len=abs(m[sum]-i);
res=max(res,len);
}
else
{ m[sum]=i;}
}
return res;}
Leave a Reply