Longest subarray with sum K

Given an array nums of size n and an integer k, find the length of the longest sub-array that sums to k. If no such sub-array exists, return 0.

Brute Force#

Try every possible subarray by fixing a start index and expanding the end index while subtracting each element from k. Whenever the remaining sum reaches 0, the current window sums to k, so we update the max length. This exhaustive scan checks all O(n²) subarrays and is correct, but leads to a Time Limit Exceeded verdict on large inputs.

class Solution{
public:
    int longestSubarray(vector<int> &nums, int k){
        int maxLen = -1;

        for(int i=0;i<nums.size();i++){
            int sum = k;
            for(int j=i;j<nums.size();j++){
                sum -= nums[j];
                if(sum==0)
                    maxLen = max(maxLen, j-i+1);
                
            }
        }
        return maxLen == -1 ? 0 : maxLen;
    }
};

Time Complexity: O(n^2) --> TLE

Space Complexity: O(1)

Optimal (Only Positives)#

The sliding window works here because all values are non-negative: expanding the window can only increase the sum, and shrinking it can only decrease the sum. Maintain two pointers, start and end; advance end to grow the window and move start forward whenever the sum exceeds k. When the sum equals k, update the longest length. Every element is visited at most twice, yielding O(n) time and O(1) space. The trade-off is that this strategy breaks when negatives are present, because shrinking the window no longer guarantees a smaller sum.

• Use Sliding window

class Solution{
public:
    int longestSubarray(vector<int> &nums, int k){
        int start = 0, end = 0;

        int longestLen = 0, sum=0;

        while(end < nums.size()){
            sum += nums[end];

            while(sum > k){
                sum -= nums[start];
                start++;
            }

            if(sum == k){
                longestLen = max(longestLen, end-start+1);
            }
        
            end++;
        }
        return longestLen;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)

Optimal Approach (Handling Positives + Negatives + Zeroes)#

Use a prefix-sum hash map to generalise the solution to any integers. At each index i, compute the cumulative prefix sum. If prefixSum - k was seen earlier at index j, then the subarray from j+1 to i sums exactly to k. Storing only the first occurrence of each prefix sum ensures we find the longest such subarray. Seeding the map with seenIdxMap[0] = -1 (the empty prefix "ends" before index 0) folds the sum == k edge case into the general lookup — no special branch required.

class Solution {
  public:
    int longestSubarray(vector<int>& arr, int k) {
        int n = arr.size();

        int prefixSum = 0;
        int len = 0;

        unordered_map<int,int> seenIdxMap;
        seenIdxMap[0] = -1;   // seed: empty prefix "ends" before index 0

        for(int i = 0; i < n; i++){
            prefixSum += arr[i];

            if(seenIdxMap.find(prefixSum - k) != seenIdxMap.end())
                len = max(len, i - seenIdxMap[prefixSum - k]);

            // only record first occurrence — earlier index = longer subarray
            if(seenIdxMap.find(prefixSum) == seenIdxMap.end())
                seenIdxMap[prefixSum] = i;
        }
        return len;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)