Longest Subarray with Sum K

Prefix sums plus a map of the earliest boundary

time O(n)space O(n)

With only positive numbers a sliding window works, because growing the window can only raise the sum and shrinking it can only lower it. One negative value destroys that guarantee: a window whose sum has overshot k may still recover later, so shrinking it throws away the answer. Prefix sums do not care about sign. Let prefix(i) be the sum of nums[0..i]; then nums[l..i] sums to k exactly when prefix(l-1) = prefix(i) - k. So walk left to right, and at each index ask whether that required earlier prefix has been seen. Store only the FIRST index at which each prefix value appeared — a later duplicate gives a nearer left edge and therefore a shorter subarray, never a longer one. Seeding the map with prefix 0 at boundary -1 is what allows the answer to start at index 0.

Details

Animated on: nums = [10,5,2,7,1,-10,9], k = 15 — find the length of the longest subarray summing to exactly k.

Problem:Longest Subarray with Sum KMedium

Prefix sums plus a map of the earliest boundary

step 1 / 9

[0]

[1]

[2]

[3]

[4]

-10

[5]

[6]

The sum of nums[l..i] is prefix(i) - prefix(l-1), because the front part nums[0..l-1] sits inside both prefixes and subtracts away. So a subarray ending at index i sums to 15 exactly when some earlier prefix equals prefix(i) - 15. That is why this walks once and looks backwards instead of trying all 28 subarrays. The empty prefix 0 is filed at boundary -1 up front — without it an answer starting at index 0 could never be found.

Pseudocode

1FUNCTION longestSubarrayWithSumK(nums, k)
2  best <- 0
3  prefix <- 0
4  firstAt <- EMPTY MAP
5  firstAt[0] <- -1
6  FOR i <- 0 TO LENGTH(nums) - 1
7    prefix <- prefix + nums[i]
8    IF prefix - k IN firstAt
9      best <- MAX(best, i - firstAt[prefix - k])
10    IF prefix NOT IN firstAt
11      firstAt[prefix] <- i
12  RETURN best

← / → step · space play · Home restart

Every step in words

Show all 9 steps

The sum of nums[l..i] is prefix(i) - prefix(l-1), because the front part nums[0..l-1] sits inside both prefixes and subtracts away. So a subarray ending at index i sums to 15 exactly when some earlier prefix equals prefix(i) - 15. That is why this walks once and looks backwards instead of trying all 28 subarrays. The empty prefix 0 is filed at boundary -1 up front — without it an answer starting at index 0 could never be found.
Prefix through index 0 is 10, so a subarray ending here would need an earlier prefix of 10 - 15 = -5 to cancel down to 15. No prefix ever hit -5, so nothing ending at index 0 sums to 15; the best length stays 0. Prefix 10 is filed at boundary 0, because a later index may need it as its partner.
Prefix through index 1 is 15, and it needs an earlier prefix of 15 - 15 = 0. That value was recorded at boundary -1, so nums[0..1] = [10, 5] sums to exactly 15, a length of 1 - (-1) = 2. That beats the previous best of 0, so the answer grows to 2.
Prefix through index 2 is 17, so a subarray ending here would need an earlier prefix of 17 - 15 = 2 to cancel down to 15. No prefix ever hit 2, so nothing ending at index 2 sums to 15; the best length stays 2. Prefix 17 is filed at boundary 2, because a later index may need it as its partner.
Prefix through index 3 is 24, so a subarray ending here would need an earlier prefix of 24 - 15 = 9 to cancel down to 15. No prefix ever hit 9, so nothing ending at index 3 sums to 15; the best length stays 2. Prefix 24 is filed at boundary 3, because a later index may need it as its partner.
Prefix through index 4 is 25, and it needs an earlier prefix of 25 - 15 = 10. That value was recorded at boundary 0, so nums[1..4] = [5, 2, 7, 1] sums to exactly 15, a length of 4 - 0 = 4. That beats the previous best of 2, so the answer grows to 4.
Prefix through index 5 is 15, and it needs an earlier prefix of 15 - 15 = 0. That value was recorded at boundary -1, so nums[0..5] = [10, 5, 2, 7, 1, -10] sums to exactly 15, a length of 5 - (-1) = 6. That beats the previous best of 4, so the answer grows to 6.
Prefix through index 6 is 24, so a subarray ending here would need an earlier prefix of 24 - 15 = 9 to cancel down to 15. No prefix ever hit 9, so nothing ending at index 6 sums to 15; the best length stays 6. Prefix 24 is not filed again — it was first seen at boundary 3, and keeping the earliest boundary is what makes every future match as long as possible.
The scan is done. The longest run summing to 15 is nums[0..5] = [10, 5, 2, 7, 1, -10], length 6. Note it stretches past the negative value -10 — a shrinking sliding window would have thrown that region away the moment the sum overshot 15, which is exactly why prefix sums are needed once negatives are allowed.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Longest Subarray with Sum K in the editor All Arrays problems Back to roadmap