.png)
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:
| Array Type | Best Approach |
|---|---|
| Only positive numbers | Sliding Window |
| Contains negative numbers | Prefix Sum + Hash Map |
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
- Initialize:
- sum = 0
- maxLen = 0
- Hash map prefixSum → index
- Traverse array:
- Add element to sum
- If sum == K:
- Update maxLen = i + 1
- If (sum - K) exists in map:
- Length = i - map[sum - K]
- Update maxLen
- 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)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
