Longest Subarray With Sum K

Problem Link - https://www.geeksforgeeks.org/problems/longest-sub-array-with-sum-k0809/1

Finding the longest subarray with sum K is a classic interview problem. The challenge becomes interesting when the array contains negative numbers, making the sliding window approach invalid.

Problem Statement

Given an array arr[] and an integer k, find the length of the longest subarray whose sum equals k.

Example

arr = [10, 5, 2, 7, 1, -10]
k = 15

Output: 6

The entire array has a sum of 15, so the longest valid subarray length is 6.

Brute Force Approach

Generate all possible subarrays, calculate their sums, and track the maximum length whenever the sum equals k.

Interview Explanation

The most straightforward approach is to consider every possible subarray. For each starting index, keep extending the subarray and calculate its sum. Whenever the sum becomes k, update the answer with the maximum length found so far.

Complexity

• Time Complexity: O(N²)
• Space Complexity: O(1)

Brute Force Code

class Solution {
    public int longestSubarray(int[] arr, int k) {

        int maxLen = 0;

        for (int i = 0; i < arr.length; i++) {

            int sum = 0;

            for (int j = i; j < arr.length; j++) {

                sum += arr[j];

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

        return maxLen;
    }
}

Optimal Approach: Prefix Sum + HashMap

Key Observation

If:

currentPrefixSum - previousPrefixSum = k

then:

previousPrefixSum = currentPrefixSum - k

So for every index, if we have already seen (currentPrefixSum - k), then the subarray between those two positions has sum k.

A HashMap helps us find previous prefix sums in O(1) time.

Why Store Only the First Occurrence?

if (!map.containsKey(sum)) {
    map.put(sum, i);
}

We store the earliest occurrence because:

length = currentIndex - earliestIndex

An earlier index always gives a longer subarray.

Optimal Java Solution

class Solution {
    public int longestSubarray(int[] arr, int k) {

        HashMap<Integer, Integer> map = new HashMap<>();

        int sum = 0;
        int maxLen = 0;

        for (int i = 0; i < arr.length; i++) {

            sum += arr[i];

            if (sum == k) {
                maxLen = i + 1;
            }

            int remaining = sum - k;

            if (map.containsKey(remaining)) {
                int length = i - map.get(remaining);
                maxLen = Math.max(maxLen, length);
            }

            // Store first occurrence only
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
        }

        return maxLen;
    }
}

Dry Run

arr = [10, 5, 2, 7]
k = 14

At index 3:

24 - 10 = 14

Since prefix sum 10 was previously seen at index 0, the subarray:

[5, 2, 7]

has sum 14.

Length:

3 - 0 = 3

Complexity Analysis

• Time Complexity: O(N)
• Space Complexity: O(N)

Key Takeaway

Whenever a problem asks for:

Subarray Sum = K and negative numbers are allowed

Think:

Current Prefix Sum - Previous Prefix Sum = K

which immediately leads to the Prefix Sum + HashMap pattern.