Longest Subarray with Sum K takes the hash-map trick from Two Sum and aims it at ranges. The move is prefix sums: turn "sum of a window" into "difference of two running totals," then look the matching total up in a map in O(1).
Problem. Given an array of integers nums and a target k, return the length of the longest
contiguous subarray whose elements sum to exactly k. If no such subarray exists, return 0.
Example: nums = [10, 5, 2, 7, 1, 9], k = 15 → answer 4 (the subarray [5, 2, 7, 1] sums to 15).
The slow way first
The obvious idea: try every subarray. Pick a start, extend an end, sum as you go, and keep the longest window that hits k. Two nested loops make that O(n²) — too slow for a large array.
The question to ask: while I am standing at index i, what do I wish I already knew? The sum of the window ending here is prefix[i] − prefix[a-1] for some earlier point a. If I want that window to equal k, then I am hoping some earlier prefix equals prefix[i] − k. A hash map answers "have I seen that prefix?" in O(1).
The idea: prefix sums plus a first-seen map
Keep a running prefix total as you sweep. At index i, a subarray ending here sums to k exactly when some earlier prefix equals need = prefix − k. If need was seen first at index j, the window nums[j+1..i] sums to k and has length i − j. Storing the first index each prefix appeared at makes that window as long as possible.
The sentinel first = {0: -1} is the key detail: it represents an empty prefix before index 0, so a subarray that starts at index 0 still gets measured. And we only store a prefix the first time we see it, because an earlier index gives a longer window.
Walk through it
Step through the animation. The pointer i sweeps left to right while prefix grows. At i = 1, prefix is 15 and need = 0 is in the map at index −1, giving length 2. Later at i = 4, prefix is 25 and need = 10 was seen at index 0, giving length 4 — the new best, the window [5, 2, 7, 1].
Pseudocode
first = {0: -1} # maps a prefix sum -> its FIRST index
prefix = 0
best = 0
for each index i with value num:
prefix += num
need = prefix - k
if need is a key in first:
best = max(best, i - first[need])
if prefix is not already a key in first:
first[prefix] = i # store only the first occurrence
return bestThe Python solution
def longest_subarray_sum_k(nums, k):
first = {0: -1}
prefix = best = 0
for i, num in enumerate(nums):
prefix += num
need = prefix - k
if need in first:
length = i - first[need]
best = max(best, length)
if prefix not in first:
first[prefix] = i
return bestfirstmaps each prefix sum to the earliest index where it occurred; the{0: -1}sentinel covers subarrays starting at index 0.prefixis the running sum of everything up to and includingi.need = prefix - kis the earlier prefix that would close a window summing to exactlyk.- Line 7 is the O(1) lookup — the heart of the trick. If
needis present, the windowfirst[need]+1 .. isums tok, and its length isi - first[need]. - We store
first[prefix] = ionly when prefix is new, so the recorded index stays the earliest one and windows stay as long as possible.
Complexity
| Case | Time | Notes |
|---|---|---|
| Brute force (every subarray) | O(n²) (slow) | nested start/end loops |
| Prefix sum + map (this solution) | O(n) (moderate) | one pass, O(1) lookups |
O(n) (moderate)We trade O(n) extra space (the prefix map) for the speed win: O(n²) → O(n). The pattern — keep a running aggregate and remember where each value first appeared — powers subarray-sum, subarray-count, and equal-zeros-and-ones problems alike.
When this pattern shows up
Whenever a problem asks about a contiguous subarray with a target sum or count, think prefix sums plus a hash map. "Subarray sum equals k," "longest subarray with equal 0s and 1s," and "contiguous array" are all the same move: store each running total and look up the one you need in O(1).
Two traps. First, seed the map with {0: -1} or windows starting at index 0 get the wrong length. Second,
store only the first time you see a prefix — overwriting with a later index would shorten your windows.
(If you instead wanted the count of subarrays, you would add up occurrences rather than keep the first index.)
Practice
At i = 4 the prefix is 25 and k = 15. What earlier prefix are we looking for, and where was it first seen?
1. Why does this solution seed the map with {0: -1}?
2. At index i, which earlier prefix sum closes a window summing to exactly k?
3. Why do we store only the FIRST index a prefix sum appears at?
4. What is the time and space complexity of the prefix-sum solution?