Longest Subarray With Sum K

Problem Statement

Given an array and a sum k, we need to print the length of the longest subarray that sums to k. (link)

Note all elements are positive.

Brute Force Approach

To identify the longest subarray with a sum of k, we can systematically generate all potential subarrays and calculate their sums. This can be accomplished efficiently using two nested loops. It's important to note that the accumulator value should be of type long to prevent potential overflow issues associated with integer data types.

Time - O(n^2)

Space - O(1)

public class Solution {
    public static int getLongestSubarray(int []a, int k) {
        Map<Long, Integer> prefixSumMap = new HashMap<>();
        int ans = 0;
        for(int i=0; i<a.length; i++){
            long accumulator =0;
            for(int j=i; j<a.length; j++){
                accumulator+=a[j];
                if(accumulator==k){
                    ans = Math.max(ans, j-i+1);
                }
            }
        }
        return ans;
    }
}

Optimal Approach

Prefix Sum:

Compute the prefix sum for each index. The sum of a subarray between any two indices can be determined by subtracting the corresponding prefix sums.

Subarray[i+1,...j] sum = prefixSum[j]-prefixSum[i]

In this approach, we traverse through the array, calculating the current sum (referred to as an accumulator). We then subtract the accumulator from the target value, representing the remaining sum or gap we are seeking. We check whether we have encountered this gap sum in previous steps, consulting a map for verification. If the map contains this sum value as a key, we retrieve the associated index value and compute the subarray length. This length is compared with the variable "ans," and if it is greater, we update "ans" with the current value. Additionally, we add the current prefix subarray sum to the map if it is not already present, associating it with the current index. If we encounter the same subarray sum again, we refrain from updating the index in the map, as we aim to find the maximum subarray length. When calculating the subarray length, we do not add one because the element present at the given prefix sum is excluded.

Time - O(n)

Space - O(n)

public class Solution {
    public static int getLongestSubarray(int []a, int k) {
        Map<Long, Integer> prefixSumMap = new HashMap<>();
        int ans = 0;
        long accumulator =0;
        for(int i=0; i<a.length; i++){
            accumulator += a[i];
            long gap = accumulator - k;
            if(gap==0){
                ans = Math.max(ans, 1+i);
            }
            if(prefixSumMap.containsKey(gap)){
                ans = Math.max(ans, i - prefixSumMap.get(gap));
            }
            if(!prefixSumMap.containsKey(accumulator)){
                prefixSumMap.put(accumulator, i);
            }
        }
        return ans;
    }
}

Optimal Approach - Positive Integers ( 2 Pointers)

If the array consists solely of positive integers, the following approach proves effective. In this method, two pointers, denoted as i and j, are maintained. Both i and j initially start at index 0. The key distinction lies in the fact that while i continues to increment, j only advances if the current sum exceeds the target sum. The rationale behind this approach is to adjust the current sum value of the target. If the current sum value is greater, the element at the jth index will be excluded from the left. Conversely, if the current sum is less than the target, i will automatically increment.

Time - O(n)

Space - O(1)

public class Solution {
    public static int longestSubarrayWithSumK(int []a, long k) {

        long currentSum = 0;
        int j=0;
        int ans = 0;
        for(int i=0; i<a.length; i++){
            currentSum+=a[i];
            if(currentSum>k){
                while(currentSum>k){
                    currentSum-=a[j];
                    j+=1;
                }
            }
            if(currentSum==k){
                ans = Math.max(ans, i-j+1);
            }
        }
        return ans;
    }
}

Another version

public class Solution {
    public static int longestSubarrayWithSumK(int []a, long k) {
        // Write your code here
        long sum = 0;
        int ans = 0;

        int j =0;

        for(int i=0; i<a.length; i++){
            sum+=a[i];

            while(sum>k){
                sum-=a[j];
                j+=1;
            }

            if(sum==k){
                ans = Math.max(ans, i-j+1);
            }
        }
        return ans;
    }
}