Problem statement
Given an integer array and a target k, return the maximum length of a contiguous subarray whose sum is k.
For [1, -1, 5, -2, 3] and k = 3, the answer is 4 because [1, -1, 5, -2] sums to 3.
Constraints & requirements
- INPUT
- Integers may include negatives
- RETURN
- Maximum matching subarray length
- TARGET
- Expected O(n) time
Examples 3 test cases
Example 1 Includes negatives
- Input
[1, -1, 5, -2, 3], k = 3- Output
4
Checks why a normal sliding window is unsafe.
Example 2 Whole array
- Input
[2, -2, 2], k = 2- Output
3
Checks the prefix sum from index zero.
Example 3 No match
- Input
[1, 2], k = 9- Output
0
Checks the missing-range result.
Hints Optional
01Describe a range with two prefixes
A subarray ending now has sum k when an earlier prefix equals currentPrefix - k.
02Keep historical lookup fast
Map each prefix sum to an index so you do not scan all earlier positions again.
03Keep the earliest index
The earliest occurrence of a prefix creates the longest possible range ending at the current index.
How to think before coding
For a fixed ending index, write rangeSum=currentPrefix−oldPrefix. Rearranging gives oldPrefix=currentPrefix−k. Since the result is a length, store an index, not a count. To maximize that length, preserve the earliest index for a total. Seed 0 at −1 so a range beginning at zero uses the same formula, then look up before recording the current boundary.
Brute force and the improvement
Choose each start and extend every end with a running sum: O(n²) time, O(1) extra space, valid with negatives too. Recomputing every range from scratch costs O(n³). Earliest-index prefix lookup reduces repeated searches to expected O(n) time with O(n) map storage. Unlike the counting problem, we store an earliest index, not a frequency, because we want maximum length.
Intuition
Let prefix be the sum from the beginning through the current index. A previous prefix of prefix - k means the values between that earlier position and the current position sum to k.
Store the earliest index for each prefix sum because the earliest position produces the longest subarray.
Java solution
import java.util.HashMap;
import java.util.Map;
public static int longestSubarrayWithSum(int[] values, long k) {
Map<Long, Integer> firstIndex = new HashMap<>();
firstIndex.put(0L, -1); // Empty prefix supports ranges beginning at index zero.
long prefix = 0; // Long avoids overflow when many int values are added.
int longest = 0;
for (int index = 0; index < values.length; index++) {
prefix += values[index]; // Sum from index zero through the current index.
// Remove an earlier prefix so the remaining contiguous range sums to k.
Integer start = firstIndex.get(prefix - k);
if (start != null) {
// The old prefix ends at start; our range begins at start + 1.
longest = Math.max(longest, index - start);
}
firstIndex.putIfAbsent(prefix, index); // Keep the earliest occurrence for maximum length.
}
return longest; // Zero remains when no matching nonempty range exists.
}When a sliding window works
If every value is nonnegative, a sliding window can solve the problem with O(1) extra space. With negative values, the window sum is not monotonic, so prefix sums are safer.
Dry run

Read the text transcript
For [1, -1, 5, -2, 3], k = 3, initialize the map with 0 → -1.
| Index | Prefix | Need prefix − 3 | Earliest matching index | Candidate length | Best |
|---|---|---|---|---|---|
| 0 | 1 | -2 | absent | none | 0 |
| 1 | 0 | -3 | absent | none | 0 |
| 2 | 5 | 2 | absent | none | 0 |
| 3 | 3 | 0 | -1 | 3 − (-1) = 4 | 4 |
| 4 | 6 | 3 | 3 | 4 − 3 = 1 | 4 |
At index 1, prefix zero appears again. Keep its original index -1, not 1. That preserves the longest range starting at index zero. Look up the old boundary before recording the current prefix.
Complexity
Expected time is O(n) and extra space is O(n).
Common mistakes
- Replacing the earliest index for a prefix sum
- Using a sliding window when negative values are allowed
- Using
intfor prefix sums when the total may overflow
Practice next
Next lessonPrefix Sum patternReview range identities and common edge cases.