Longest Subarray With Sum K

Arrays, Two Pointers, Hash Tables

Problem Statement:
Given a array of N elements. Find the length of Longest Subarray whose sum is equal to given K.

Problem Link: Coding Ninjas

Brute-force Approach:
We have to find the subarray with sum equal to K. Let’s use prefix sum technique to get all possible sums from 0 to N.

1. Define sum to add each element in the array one by one and store it in hash table with key as sum and index as value.
2. Define max_len to store maximum length of subarray which sum up to K.
3. Iterate through the array. Add current element in array to sum.
4. We’ll store the sum with it’s index value. This means that the addition of elements in 0 to i interval is sum.
   Note: if sum is already present in the hashtable means the current element is zero, for this we’ll take minimum of both index because we need maximum length possible.
5. Then, we’ll find req_sum which is nothing but difference between sum and K. Let’s check whether req_sum is present in hashtable. if it’s present which means there is a interval which can sum up to K.
6. We’ll take maximum of max_len to the current interval by subtracting the sum index and current index.

int longestSubarrayWithSumK(vector<int> a, long long k) {

    long long n = a.size(), sum = 0;
    int max_len = 0;
    map<int, int> mp;

    for(int i = 0; i < n; i++){
        sum += a[i];
      
        if(mp.find(sum) != mp.end()){
            mp[sum] = min(mp[sum], i); // to handle zeros
        }else{
            mp[sum] = i;
        }

        int req_sum = sum - k;
        
        if(req_sum == 0){
            max_len = max(max_len, i + 1);
        }

        if(mp.find(req_sum) != mp.end()){
            max_len = max(max_len, i - mp[req_sum]);
        }

    }
    return max_len;
}

Time Complexity:
O(N) — where N is number of elements in the array

Space Complexity:
O(N) — storing sum elements of every index in a hash table.

Optimal Approach:
The focus of this approach is to remove hash table to store prefix sums. In this approach, we’ll use sliding window to find the subarray.

1. Let’s take two pointers l and r .
2. Define sum to store prefix sum in single variable. Add the current element with sum and store it a variable possible_sum
3. Check whether the possible_sum has become greater than K. If it is, subtract possible_sum with element in l position. Repeat until possible_sum become lesser than or equal to K.
4. Check possible_sum is equal to K. If this condition satisfies, we’ll calculate the subarray length by (r — l + 1) means the elements in the interval from l to r has sum which is equal to K.
5. Replace sum with possible_sum to move forward with next iteration.
6. Repeat until r exceeds N.

int longestSubarrayWithSumK(vector<int> a, long long k) {
    int l = 0, sum = 0;
    
    for(int r = 0; r < n; r++){

        long long possible_sum = sum + a[r];
        
        while(possible_sum > k){
            possible_sum -= a[l];
            l++;
        }

        if(possible_sum == k){
            max_len = max(max_len, r - l + 1);
        }

        sum = possible_sum;

    }
}

Time Complexity:
O(N) — where N is number of elements in the array.

Space Complexity:
O(1) — no extra space is required.