Subarray Sum Equals K
Prefix sums plus a map of what has been seen
The instinct is a sliding window, and with a negative number in the array that instinct is wrong: adding an element can make the sum smaller, so the window never knows when to shrink. Prefix sums fix that. Let prefix(i) be the sum of nums[0..i]; then the sum of nums[l..r] is prefix(r) - prefix(l-1), because the front part nums[0..l-1] sits inside both and cancels. So a subarray ending at r has sum k exactly when some earlier prefix equals prefix(r) - k. Walk once, keep a map from prefix value to how many times it has occurred, and every index contributes its matching count in constant time. Seeding that map with prefix 0 is what allows a match to start at index 0 — the step most implementations forget.
Details
Animated on: nums = [1,2,3,-3,1,1,1], k = 3 — count the subarrays whose sum is exactly k.
Problem:Subarray Sum Equals KMedium
Pattern:Prefix Sum
Prefix sums plus a map of what has been seen
step 1 / 9
The sum of nums[l..r] is prefix(r) - prefix(l-1), because the shared front part nums[0..l-1] is inside both prefixes and subtracts away. So a subarray ending at r sums to 3 exactly when some earlier prefix equals prefix(r) - 3. That turns "try every pair of endpoints" into one left-to-right walk. The empty prefix 0 is filed before the walk starts, otherwise a subarray beginning at index 0 could never be counted.
1FUNCTION countSubarraysWithSum(nums, k)2 count <- 03 prefix <- 04 seen <- EMPTY MAP5 seen[0] <- 16 FOR r <- 0 TO LENGTH(nums) - 17 prefix <- prefix + nums[r]8 need <- prefix - k9 IF need IN seen10 count <- count + seen[need]11 seen[prefix] <- seen[prefix] + 112 RETURN count
← / → step · space play · Home restart
Every step in words
Show all 9 steps
- The sum of nums[l..r] is prefix(r) - prefix(l-1), because the shared front part nums[0..l-1] is inside both prefixes and subtracts away. So a subarray ending at r sums to 3 exactly when some earlier prefix equals prefix(r) - 3. That turns "try every pair of endpoints" into one left-to-right walk. The empty prefix 0 is filed before the walk starts, otherwise a subarray beginning at index 0 could never be counted.
- Adding nums[0] = 1 makes the running prefix 1, so the partner it needs is 1 - 3 = -2. No earlier prefix ever equalled -2, so nothing ending at index 0 sums to 3 and the count stays 0. Prefix 1 is filed anyway — a later index may need it as its own partner.
- Adding nums[1] = 2 makes the running prefix 3, so the partner it needs is 3 - 3 = 0. That prefix value was recorded 1 time already, and each occurrence marks a place a matching subarray can start: nums[0..1] = [1, 2]. Everything before those points cancels, leaving sum 3, so the count rises to 1.
- Adding nums[2] = 3 makes the running prefix 6, so the partner it needs is 6 - 3 = 3. That prefix value was recorded 1 time already, and each occurrence marks a place a matching subarray can start: nums[2..2] = [3]. Everything before those points cancels, leaving sum 3, so the count rises to 2.
- Adding nums[3] = -3 makes the running prefix 3, so the partner it needs is 3 - 3 = 0. That prefix value was recorded 1 time already, and each occurrence marks a place a matching subarray can start: nums[0..3] = [1, 2, 3, -3]. Everything before those points cancels, leaving sum 3, so the count rises to 3.
- Adding nums[4] = 1 makes the running prefix 4, so the partner it needs is 4 - 3 = 1. That prefix value was recorded 1 time already, and each occurrence marks a place a matching subarray can start: nums[1..4] = [2, 3, -3, 1]. Everything before those points cancels, leaving sum 3, so the count rises to 4.
- Adding nums[5] = 1 makes the running prefix 5, so the partner it needs is 5 - 3 = 2. No earlier prefix ever equalled 2, so nothing ending at index 5 sums to 3 and the count stays 4. Prefix 5 is filed anyway — a later index may need it as its own partner.
- Adding nums[6] = 1 makes the running prefix 6, so the partner it needs is 6 - 3 = 3. That prefix value was recorded 2 times already, and each occurrence marks a place a matching subarray can start: nums[2..6] = [3, -3, 1, 1, 1] and nums[4..6] = [1, 1, 1]. Everything before those points cancels, leaving sum 3, so the count rises to 6.
- One pass, each index asked once, 6 subarrays summing to 3. 3 of them contain the negative entry nums[3] = -3, which is exactly where a two-pointer window breaks down: once the running sum passes 3 a window would shrink from the left, yet extending across a negative value can bring the sum back down to 3. The prefix map never has to make that call — it only asks whether the needed earlier prefix was ever seen, which is O(1) per index and O(n) overall against the O(n^2) of summing all 28 subarrays.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.