Longest Subarray with Sum K
Longest Subarray with Sum K is a GFG problem (LeetCode has it as premium problem 325, Maximum Size Subarray Sum Equals k). You are given an integer array arr and an integer k. Return the length of the longest subarray whose elements add up to exactly k, or 0 if there is none.
- A subarray is a contiguous run of elements.
- The array may contain negative numbers and zeros. That one detail decides the whole approach.
ncan be 10⁵, so checking all n² subarrays is too slow; the target is one pass.
- 1 <= n <= 10⁵
- -10⁵ <= nums[i] <= 10⁵
- -10⁹ <= k <= 10⁹
- Negative values are allowed, so a shrinking window will not work
Intuition
Finding the longest subarray with given sum k directly means checking every pair (start, end), which is O(n²). A prefix sum cuts it to one pass.
Let prefix[i] be the sum of arr[0..i]. Then
sum(arr[j+1..i]) = prefix[i] - prefix[j]
so a subarray ending at i sums to k exactly when some earlier prefix equals prefix[i] - k. The question "which start works?" becomes a single hash-map lookup, and the map only needs to remember where each prefix value first appeared.
"Subarray" plus "sum equals k" plus negative numbers allowed means prefix sums with a hash map. If every number were positive, a sliding window would do the same job in O(1) space, because growing the window could only raise the sum. Negatives break that, so the window has no rule for which end to move.
Approach
Before reading on: write sum(arr[j+1..i]) in terms of two prefix sums. Then decide what the hash map should store for the longest subarray, and what it must contain before the loop starts.
Two ways to solve it
Keep a running prefix sum and the first index of every prefix value; look up prefix - k at each step.
- Speed: one pass, O(1) average per element.
- Negatives: handled, nothing assumes order.
- Space: the map can hold n + 1 prefixes.
The standard answer for any integers.
Fix each start i, extend the end j while adding to a running total, and record j - i + 1 whenever the total is k.
- Simple: two loops, no map.
- Scale: about 5 × 10⁹ additions at n = 10⁵.
- Use: a checker for small tests.
Correct, but too slow on the full limits.
The map replaces the inner loop with one lookup, turning O(n²) into O(n) while still allowing negatives. The steps, code and live demo below follow the prefix-sum method, and the brute-force code is further down.
Seed the map
first = {0: -1}, prefix = 0, best = 0. The 0 → -1 entry stands for the empty prefix before index 0, so a subarray that starts at index 0 can be found too.
Extend the prefix sum
For each index i, add arr[i] to prefix. It now holds the sum of arr[0..i]. One running total replaces recomputing each subarray's sum, which is what makes the pass O(n).
Look up the partner prefix
If prefix - k is in the map at index j, then arr[j+1..i] sums to k and has length i - j. Update best with it. A subarray ending at i sums to k exactly when an earlier prefix equals prefix - k, so one lookup checks every possible start at once. Look it up before storing the current prefix, so with k = 0 an index can never match itself.
Store the prefix only if it is new
If prefix is not in the map, store first[prefix] = i. Never overwrite an existing entry. The earliest index of a prefix value gives the longest subarray, so later repeats are never better.
Return best
After one pass, best is the longest length found, or 0 if no lookup ever succeeded. Every subarray ends at some index, and each ending index was checked once with its best start.
Longest Subarray with Sum K solution in Python | C++ | Java
sum(arr[j+1..i]) = prefix[i] - prefix[j]. So at each index, ask the map whether the value prefix - k appeared earlier. The seed {0: -1} is the empty prefix, so a subarray starting at index 0 can be found too.arr[0..1], add up to exactly 15. Its length is 1 + 1 = 2, the best so far. Store 15 → 1 so later indices can use it as a start point.arr[1..4], add up to exactly 15. Its length is 4 - 0 = 4, the best so far. Store 25 → 4 so later indices can use it as a start point.[5, 2, 7, 1], length 4. Every index did one lookup and at most one insert, so the whole scan is O(n).sum(arr[j+1..i]) = prefix[i] - prefix[j]. So at each index, ask the map whether the value prefix - k appeared earlier. The seed {0: -1} is the empty prefix, so a subarray starting at index 0 can be found too.arr[0..3], add up to exactly 3. Its length is 3 + 1 = 4, the best so far. Store 3 → 3 so later indices can use it as a start point.arr[4..4] sums to 3 too, but its length 1 does not beat 4, so best stays. Store 6 → 4 so later indices can use it as a start point.[1, -1, 5, -2], length 4. Every index did one lookup and at most one insert, so the whole scan is O(n).sum(arr[j+1..i]) = prefix[i] - prefix[j]. So at each index, ask the map whether the value prefix - k appeared earlier. The seed {0: -1} is the empty prefix, so a subarray starting at index 0 can be found too.arr[1..1], add up to exactly 1. Its length is 1 - 0 = 1, the best so far. The prefix 0 was already seen at index -1. Keeping that earlier index is what makes future matches as long as possible; overwriting it with 1 would shorten them.arr[0..2], add up to exactly 1. Its length is 2 + 1 = 3, the best so far. Store 1 → 2 so later indices can use it as a start point.[-1, 1, 1], length 3. Every index did one lookup and at most one insert, so the whole scan is O(n).Brute force over every start
For each start index the inner loop grows the subarray one element at a time, keeping its sum in total, so every subarray is summed in O(1) extra work.
Common pitfalls
Using a sliding window when negatives are allowed
while window_sum > k:
window_sum -= arr[lo]
lo += 1if prefix - k in first:
best = max(best, i - first[prefix - k])Shrinking on overshoot assumes that dropping an element lowers the sum. For [1, -1, 5, -2, 3] and k = 3, dropping -1 raises it, so the window throws away the start of the answer [1, -1, 5, -2] and returns 0 instead of 4.
Overwriting the index of a repeated prefix
first[prefix] = i
if prefix not in first:
first[prefix] = iIn [-1, 1, 1] with k = 1 the prefix 0 appears at the seed (-1) and again at index 1. Overwriting moves it to 1, so the final lookup gives length 1 instead of 3.
Forgetting the {0: -1} seed
first = {}first = {0: -1}A subarray that starts at index 0 needs the empty prefix as its partner. For [3, 1] and k = 4 the only answer is the whole array, and without the seed the result is 0.
Edge cases
With n = 10⁵ and values up to 10⁵ in size, prefix sums can reach 10¹⁰. C++ and Java keep prefix and the map keys as 64-bit.
Complexity
Longest vs count, negatives vs positives
Three problems that look alike; the values and the question decide the tool.
| Problem | Values | Method | Map stores |
|---|---|---|---|
| Longest subarray with sum k | any, including negatives | prefix sum + hash map | first index of each prefix |
| Longest subarray with sum k | all positive | sliding window, O(1) space | nothing |
| Count subarrays with sum k (LeetCode 560) | any | prefix sum + hash map | how many times each prefix occurred |
Longest Subarray with Sum K FAQ
How do you find the longest subarray with sum k?
- Idea:
sum(arr[j+1..i]) = prefix[i] - prefix[j], so look for an earlier prefix equal toprefix[i] - k. - Map: prefix value → first index where it appeared, seeded with
{0: -1}. - Loop: add
arr[i]toprefix; ifprefix - kis in the map atj, updatebestwithi - j; storeprefixonly if it is new. - Complexity: O(n) time, O(n) space.
- Example:
[10, 5, 2, 7, 1, 9], k = 15 gives 4 for[5, 2, 7, 1].
Is there a longest subarray with sum k LeetCode problem?
Yes, as LeetCode 325, Maximum Size Subarray Sum Equals k, which is a premium problem. LeetCode 560, Subarray Sum Equals K, is the free counting version: the same prefix-sum idea, but the map stores counts.