Longest Subarray with Sum K
Given an array (may contain negatives) and a target k, return the length of the longest subarray whose elements sum to exactly k.
Intuition
Every subarray sum is a difference of two prefix sums: sum(i..j) = pre[j] − pre[i−1]. So a subarray sums to k exactly when the current prefix minus some earlier prefix equals k. Store the first index where each prefix value occurred, and each new prefix asks: have I seen prefix − k before?
Prefix sums plus a hash map of earliest index per prefix value. The identity is sum(i..j) = pre[j] - pre[i-1], so finding a subarray summing to k means finding an earlier prefix equal to pre - k. Storing only the first occurrence is what makes the found subarray as long as possible.
Approach
Why sliding window fails here
With negatives, growing the window can shrink the sum and shrinking can grow it — the window has no monotone signal to steer by. We need something that works for arbitrary signs: prefix sums.
Prefix sums turn subarrays into pairs
Walk once keeping the running sum pre. If some earlier prefix equaled pre − k, the elements after that point sum to exactly k. A hash map from prefix value → earliest index answers that in O(1).
Keep only the first occurrence
For the longest subarray we want the earliest index where each prefix value appeared, so never overwrite an existing entry. Seed the map with {0: -1} so subarrays starting at index 0 are counted.
Solution & live demo
Common pitfalls
Overwriting an existing prefix index
first[pre] = i
if pre not in first:
first[pre] = iFor maximum length you want the earliest index that produced this prefix. Overwriting keeps the most recent one, which yields the shortest matching subarray instead of the longest.
Omitting the {0: -1} seed
first = {}first = {0: -1}A subarray starting at index 0 needs an empty prefix to subtract against, and its index must be -1 so the length computes as i - (-1) = i + 1. Without the seed, any answer beginning at the start is missed.
Assuming this works for all-positive arrays only
# sliding window with shrink-on-overshoot
if pre - k in first:
best = max(best, i - first[pre - k])A sliding window is valid only when every element is positive, since it relies on the sum growing monotonically. With negatives present the window may need to shrink and grow unpredictably — prefix sums handle both cases.
Edge cases
The seed {0: -1} makes pre == k yield length i − (−1) = i + 1.
Keep the first index only — a later duplicate would only shorten the candidate subarray.