Subarray Sum Equals K —
Prefix sum + hash map. One pass.
Count the number of contiguous subarrays whose elements sum to k. Brute force is O(n²). Prefix sum plus a hash map solves it in O(n) — for each prefix sum, check if prefix - k has been seen before. Watch the prefix sum grow and the complement lookup fire on LearnBug and the connection clicks instantly.
The core insight
A subarray from index i to j has sum equal to k when prefix[j] - prefix[i-1] = k, which means prefix[i-1] = prefix[j] - k. So at each position j, you just need to know: how many times has the value prefix[j] - k appeared as a prefix sum before? A hash map stores prefix sum counts for O(1) lookup.
Why this is hard to see without visualization
The math feels abstract — you're not looking at subarrays at all, just prefix sums and complements. On LearnBug you see the prefix sum accumulate in real time, the map update at each step, and the count increment when a complement is found. The "invisible subarrays" become visible as pairs of prefix sum positions.
Array [1, 2, 3, -2, 2], k=3. Answer: 4
Map stores { prefix_sum: count }. Initialise with { 0: 1 } (empty prefix).
Initialise prefix=0, count=0, map={0:1}
The {0:1} entry handles subarrays starting at index 0. A prefix sum of k means the subarray from index 0 covers it — we need prefix - k = 0 to have count 1.
i=0, val=1. prefix=1. complement=1-3=-2. -2 not in map.
No subarray ending here sums to 3. Add prefix 1 to map.
i=1, val=2. prefix=3. complement=3-3=0. 0 IS in map! count += 1
Map[0]=1 → found 1 subarray summing to 3 (the subarray [1,2]). count=1. Add prefix 3 to map.
i=2, val=3. prefix=6. complement=6-3=3. 3 IS in map! count += 1
Map[3]=1 → found subarray [3] (just element at index 2). count=2. Add prefix 6.
i=3, val=-2. prefix=4. complement=4-3=1. 1 IS in map! count += 1
Map[1]=1 → found subarray [2,3,-2] (indices 1-3). count=3.
i=4, val=2. prefix=6. complement=6-3=3. 3 IS in map! count += 1
Map[3]=1 → found subarray [3,-2,2] (indices 2-4). count=4. Final answer.
Time & Space Complexity
Frequently asked questions
Why do we initialise the map with {0:1}?
Consider the subarray starting at index 0. Its sum is prefix[j]. For this to equal k, we need prefix[j] - k = 0 to be in the map. Without {0:1}, we'd never count subarrays that begin at the very start of the array. The 0 represents the "empty prefix" before any element is added.
Why doesn't sliding window work here?
The sliding window technique for subarray sums requires all elements to be non-negative — so expanding the window always increases the sum and shrinking always decreases it. With negative numbers, expanding can decrease the sum, making the two-pointer movement ambiguous. The prefix sum + hash map approach handles any integers.
What does "complement" mean in this context?
The complement is prefix[j] - k. If this value has appeared as a prefix sum at some earlier index i, then the subarray from i+1 to j has sum exactly k. We're asking: "has there been a point where the running total was k less than it is now?" Each such point defines one valid subarray.
Why do we add prefix_count[prefix] AFTER checking?
Adding the current prefix to the map before checking would allow a subarray of zero length (using the same index as both endpoints) to be counted. We check first, then record — ensuring only previous prefix sums contribute to the count at the current index.
What is the LeetCode problem for this?
LeetCode 560 — Subarray Sum Equals K. Medium difficulty and a very commonly asked interview problem. Variants include: LC 523 (Continuous Subarray Sum — divisible by k), LC 974 (Subarray Sums Divisible by K), and LC 325 (Maximum Size Subarray Sum Equals k). All use the same prefix sum + hash map pattern.
Watch prefix sum grow and complements fire on your array
Paste your array and k into LearnBug and see every subarray counted step by step.