Longest Subarray with Sum K

Problem Statement

Given an array of integers and an integer K, find the length of the longest contiguous subarray whose sum is exactly equal to K.

If no such subarray exists, return 0.

Why This Problem Is Important

• Very common interview question
• Tests understanding of:
  • Prefix Sum
  • Hashing
  • Sliding Window logic
• Extension of:
  • Subarray with Given Sum
  • Two Sum
  • Kadane’s concepts

Example 1 (Positive + Negative Numbers)

Input

arr = [10, 5, 2, 7, 1, 9]
K = 15

Output

4

Explanation

Subarray: [5, 2, 7, 1]
Sum = 15
Length = 4 (longest)

Example 2

Input

arr = [1, -1, 5, -2, 3]
K = 3

Output

4

Explanation

Subarray: [1, -1, 5, -2]

Key Observation

The approach depends on array elements:

Approach 1: Prefix Sum + Hash Map (Works for All Cases)

Core Idea

If:

prefixSum[j] - prefixSum[i] = K

Then:

prefixSum[i] = prefixSum[j] - K

To get the longest length, we:

• Store the first occurrence of each prefix sum
• Do not overwrite existing sums

Algorithm

1. Initialize:
   • sum = 0
   • maxLen = 0
   • Hash map prefixSum → index
2. Traverse array:
   • Add element to sum
3. If sum == K:
   • Update maxLen = i + 1
4. If (sum - K) exists in map:
   • Length = i - map[sum - K]
   • Update maxLen
5. Store sum in map only if not already present

Time and Space Complexity

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

C Implementation

#include <stdio.h>

int main() {
    int arr[] = {10, 5, 2, 7, 1, 9};
    int n = 6, K = 15;

    int sum = 0, maxLen = 0;
    int prefixSum[1000];
    int index[1000];
    int size = 0;

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

        if(sum == K)
            maxLen = i + 1;

        for(int j = 0; j < size; j++) {
            if(prefixSum[j] == sum - K) {
                int len = i - index[j];
                if(len > maxLen)
                    maxLen = len;
            }
        }

        int found = 0;
        for(int j = 0; j < size; j++) {
            if(prefixSum[j] == sum)
                found = 1;
        }

        if(!found) {
            prefixSum[size] = sum;
            index[size] = i;
            size++;
        }
    }

    printf("Longest subarray length: %d", maxLen);
    return 0;
}

Output

Longest subarray length: 4

C++ Implementation

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    int arr[] = {10, 5, 2, 7, 1, 9};
    int n = 6, K = 15;

    unordered_map<int, int> mp;
    int sum = 0, maxLen = 0;

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

        if(sum == K)
            maxLen = i + 1;

        if(mp.find(sum - K) != mp.end())
            maxLen = max(maxLen, i - mp[sum - K]);

        if(mp.find(sum) == mp.end())
            mp[sum] = i;
    }

    cout << "Longest subarray length: " << maxLen;
    return 0;
}

Java Implementation

import java.util.*;

public class LongestSubarraySumK {
    public static void main(String[] args) {
        int[] arr = {10, 5, 2, 7, 1, 9};
        int K = 15;

        Map map = new HashMap<>();
        int sum = 0, maxLen = 0;

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

            if(sum == K)
                maxLen = i + 1;

            if(map.containsKey(sum - K))
                maxLen = Math.max(maxLen, i - map.get(sum - K));

            map.putIfAbsent(sum, i);
        }

        System.out.println("Longest subarray length: " + maxLen);
    }
}

Python Implementation

arr = [10, 5, 2, 7, 1, 9]
K = 15

prefix_map = {}
sum_val = 0
max_len = 0

for i, num in enumerate(arr):
    sum_val += num

    if sum_val == K:
        max_len = i + 1

    if sum_val - K in prefix_map:
        max_len = max(max_len, i - prefix_map[sum_val - K])

    if sum_val not in prefix_map:
        prefix_map[sum_val] = i

print("Longest subarray length:", max_len)

Dry Run

arr = [10, 5, 2, 7, 1, 9], K = 15

Index | Element | Sum | sum-K | MaxLen
0     | 10      | 10  | -5    | 0
1     | 5       | 15  | 0     | 2
2     | 2       | 17  | 2     | 2
3     | 7       | 24  | 9     | 2
4     | 1       | 25  | 10    | 4
5     | 9       | 34  | 19    | 4

Approach 2: Sliding Window (Only Positive Numbers)

Note

This fails for negative numbers, so it is not preferred unless explicitly stated.

• Time: O(n)
• Space: O(1)

C Implementation

#include<stdio.h>

int main() {
    int arr[] = {1, 2, 3, 7, 5};
    int n = 5, K = 12;

    int start = 0, sum = 0, maxLen = 0;

    for (int end = 0; end < n; end++) {
        sum += arr[end];

        while (sum > K && start <= end) {
            sum -= arr[start];
            start++;
        }

        if (sum == K) {
            int len = end - start + 1;
            if (len > maxLen)
                maxLen = len;
        }
    }

    printf("Longest subarray length: %d", maxLen);
    return 0;
}

Output

Longest subarray length: 3

C++ Implementation

#include<iostream>
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 7, 5};
    int n = 5, K = 12;

    int start = 0, sum = 0, maxLen = 0;

    for (int end = 0; end < n; end++) {
        sum += arr[end];

        while (sum > K && start <= end) {
            sum -= arr[start++];
        }

        if (sum == K) {
            maxLen = max(maxLen, end - start + 1);
        }
    }

    cout << "Longest subarray length: " << maxLen;
    return 0;
}

Output

Longest subarray length: 3

Java Implementation

public class LongestSubarraySlidingWindow {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 7, 5};
        int K = 12;

        int start = 0, sum = 0, maxLen = 0;

        for (int end = 0; end < arr.length; end++) {
            sum += arr[end];

            while (sum > K && start <= end) {
                sum -= arr[start++];
            }

            if (sum == K) {
                maxLen = Math.max(maxLen, end - start + 1);
            }
        }

        System.out.println("Longest subarray length: " + maxLen);
    }
}

Python Implementation

arr = [1, 2, 3, 7, 5]
K = 12

start = 0
sum_val = 0
max_len = 0

for end in range(len(arr)):
    sum_val += arr[end]

    while sum_val > K and start <= end:
        sum_val -= arr[start]
        start += 1

    if sum_val == K:
        max_len = max(max_len, end - start + 1)

print("Longest subarray length:", max_len)

JavaScript Implementation

let arr = [1, 2, 3, 7, 5];
let K = 12;

let start = 0, sum = 0, maxLen = 0;

for (let end = 0; end < arr.length; end++) {
    sum += arr[end];

    while (sum > K && start <= end) {
        sum -= arr[start++];
    }

    if (sum === K) {
        maxLen = Math.max(maxLen, end - start + 1);
    }
}

console.log("Longest subarray length:", maxLen);

Summary

• Subarray must be continuous
• Prefix Sum + Hash Map gives:
  • Optimal time
  • Works for all cases
• Store first occurrence only to maximize length
• Very common follow-up after:
  • Subarray with Given Sum
  • Kadane’s Algorithm

Next Problems in the series

Rearrange Array Alternately (Max–Min)