Longest Sub-Array with Sum K

Problem Statement

Given an array containing N integers and an integer K., Your task is to find the length of the longest Sub-Array with the sum of the elements equal to the given value K.

Example 1:

Input :
A[] = {10, 5, 2, 7, 1, 9}
K = 15
Output : 4
Explanation:
The sub-array is {5, 2, 7, 1}.

Example 2:

Input : 
A[] = {-1, 2, 3}
K = 6
Output : 0
Explanation: 
There is no such sub-array with sum 6.

Your Task: This is a function problem. The input is already taken care of by the driver code. You only need to complete the function lenOfLongSubarr() that takes an array (A), sizeOfArray (n), sum (K)and returns the required length of the longest Sub-Array. The driver code takes care of the printing.

Expected Time Complexity: O(N). Expected Auxiliary Space: O(N).

Constraints: 1<=N<=105 -105<=A[i], K<=105

Intuition

Carry prefix sum
Store each element in map 

And check if Prefix sum - k exists in map
Update length accordingly

"Check out the solution in this: Prefix sum for K=0  and using running sum we calculate the answer

Zero is put in advance to find eg- sum=15 and K=15 then sum-K = 0 ;
To find this difference in hash

As an when we 
index  -1|  0   1   2    3   4   5 
arr[i]   0  |10   5   2   7    1   9
sum   0  | 10 15 17 24 25 34

Everytime we encounter the sum we get last index 
check for eg
at index 4 25-15 10 we fall on last sum

"

Links

https://practice.geeksforgeeks.org/problems/longest-sub-array-with-sum-k0809/1

Video Links

https://www.youtube.com/watch?v=yDeNqw_dAU0

Approach 1:

C++

class Solution{
    public:
    int lenOfLongSubarr(int A[],  int N, int K) 
    { 
        map<int,int>mp;
        int sum=0;
        mp[0]=-1;   // for case of -2 1 1
        int l=0;            //prefix sum   -2 -1 0  but to see 0 in hash we have to put it first          
        
        // 10 5  2  7  1  9
        // 10 15 17 24 25 34
        
        for(int i=0;i<N;i++){
            sum+=A[i];
            
            if(mp.find(sum-K)!=mp.end()){
               l=max(l,i-mp[sum-K]);
            }
            
            if(mp.find(sum)==mp.end())
            {
                mp[sum]=i;
            }
            
        }
        
        return l;
        
    } 


};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems