Pattern visualizer
Longest Subarray with Sum K
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. Animated on: nums = [10,5,2,7,1,-10,9], k = 15 — find the length of the longest subarray summing to exactly k..
Prefix sums plus a map of the earliest boundary
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.
1FUNCTION longestSubarrayWithSumK(nums, k)2 best <- 03 prefix <- 04 firstAt <- EMPTY MAP5 firstAt[0] <- -16 FOR i <- 0 TO LENGTH(nums) - 17 prefix <- prefix + nums[i]8 IF prefix - k IN firstAt9 best <- MAX(best, i - firstAt[prefix - k])10 IF prefix NOT IN firstAt11 firstAt[prefix] <- i12 RETURN best
← / → step · space play · Home restart