Subarray Sum Equals K (LeetCode 560)
You have an array of integers nums and a target integer k. Count how many contiguous, non-empty subarrays of nums add up to exactly k, and return that count.
Worked Examples
nums = [1,1,1], k = 22[1,1] at positions 0-1 and [1,1] at positions 1-2 both sum to 2.nums = [1,2,3], k = 32[1,2] and [3] both sum to 3.⚖️Formal Constraints & Bounds
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
Core Insight
prefix[j] - prefix[i] = k implies prefix[i] = prefix[j] - k. By caching seen prefix sum frequencies in a hash table (Key: The running sum. Value: The number of times we've seen it.) initialized with {0: 1}, we resolve all valid left boundaries in single-pass O(N) time.
Real-World Scenario & Production Applications
Financial ledger auditing and telemetry delta balancing where transaction deltas can be positive or negative.
Subproblems & Recurrence Decomposition3 Phases
Maintain running prefix sum curr_sum and a hash map prefix_counts = {0: 1} tracking frequencies of previously seen prefix sums (Key: The running sum. Value: The number of times we've seen it.).
prefix_counts = {0: 1} # Base state: empty prefix sum = 0
# Key: The running sum.
# Value: The number of times we've seen it.
curr_sum = 0
count = 0Step-by-Step Execution Trace Table
Index i | nums[i] | Running Sum (curr) | Query Needed (curr - k) | Matches in Map | Updated Total Count | Hash Map State {sum: freq} |
|---|---|---|---|---|---|---|
| Init | — | 0 | — | — | 0 | {0: 1} |
0 | 1 | 1 | 1 - 2 = -1 | 0 | 0 | {0: 1, 1: 1} |
1 | -1 | 0 | 0 - 2 = -2 | 0 | 0 | {0: 2, 1: 1} |
2 | 1 | 1 | 1 - 2 = -1 | 0 | 0 | {0: 2, 1: 2} |
3 | 1 | 2 | 2 - 2 = 0 | 2 ([0,3], [2,3]) | 0 + 2 = 2 | {0: 2, 1: 2, 2: 1} |
4 | 1 | 3 | 3 - 2 = 1 | 2 ([1,4], [3,4]) | 2 + 2 = 4 | {0: 2, 1: 2, 2: 1, 3: 1} |
The Math, Step by Step
1. The numbers the code compares
Call the prefix sum at : the total of the first elements of nums. So , because it adds no elements. The subarray from index to index has this total:
The code walks through nums once. After it adds nums[R], the variable running_sum holds . The question for this step is: how many subarrays end at index and have total k?
2. Turning "total equals k" into a lookup
A subarray from to has total k exactly when
The right side is known at step . The code calls it needed_prefix = running_sum - k. So the number of subarrays that end at with total k equals the number of earlier prefix sums , with , that are equal to needed_prefix.
The code keeps those earlier prefix sums in a hash map, prefix_counts. prefix_counts[s] is how many of are equal to . One lookup, prefix_counts[needed_prefix], counts every matching start at once.
3. Why this counts every subarray exactly once
Every subarray has exactly one end index and one start index . The code counts it at step , when running_sum is and the map holds . So each subarray is counted once, at its own end.
The rule comes from subtracting two totals. It does not need the values to be positive. That is why the code works with negative numbers in nums. A sliding window cannot do this: with negative values, a longer window can have a smaller total, so the window cannot decide when to shrink.
4. The two lines whose order matters
The base case prefix_counts[0] = 1. It stores , the empty prefix, before the loop. Without it, subarrays that start at index 0 are never counted. In Example 2, nums = [1,2,3] and k = 3, the subarray [1,2] starts at index 0. Its total is found as . Without the stored , the code returns 1 instead of 2.
Look up first, then store. The code checks needed_prefix before it runs prefix_counts[running_sum] += 1. So at step the map holds only , and every match has . If the code stored first, then k = 0 would match with itself. That match is the empty subarray, which the problem does not count. For nums = [1] and k = 0, the store-first order returns 1, and the correct answer is 0.
5. Example 1 by hand
nums = [1,1,1], k = 2. Before the loop, prefix_counts = {0: 1}.
num | running_sum | needed_prefix | prefix_counts before the lookup | Added to total_matches | total_matches | |
|---|---|---|---|---|---|---|
| 0 | 1 | 1 | {0: 1} | 0 | 0 | |
| 1 | 1 | 2 | {0: 1, 1: 1} | 1 | 1 | |
| 2 | 1 | 3 | {0: 1, 1: 1, 2: 1} | 1 | 2 |
At , the match is , so the subarray is indices 0 to 1. At , the match is , so the subarray is indices 1 to 2. The code returns 2, the expected output.
6. Example 2 by hand
nums = [1,2,3], k = 3. Before the loop, prefix_counts = {0: 1}.
num | running_sum | needed_prefix | prefix_counts before the lookup | Added to total_matches | total_matches | |
|---|---|---|---|---|---|---|
| 0 | 1 | 1 | {0: 1} | 0 | 0 | |
| 1 | 2 | 3 | {0: 1, 1: 1} | 1 | 1 | |
| 2 | 3 | 6 | {0: 1, 1: 1, 3: 1} | 1 | 2 |
At , the match is , which gives [1,2]. At , the match is , which gives [3]. The code returns 2, the expected output.
7. From the formulas to the code
| Formula | In subarraySum |
|---|---|
| is stored once | prefix_counts[0] = 1 |
running_sum += num | |
needed_prefix = running_sum - k | |
count of earlier equal to needed_prefix | total_matches += prefix_counts[needed_prefix] |
| store after the lookup | prefix_counts[running_sum] += 1 |
Each step does one lookup and one store in the hash map, so the whole pass takes time. The map holds at most different prefix sums, so it takes space.
| 1 | prefix_counts = defaultdict(int) |
| 2 | prefix_counts[0] = 1 |
| 3 | running_sum = 0 |
| 4 | total_matches = 0 |
| 5 | for num in nums: |
| 6 | running_sum += num |
| 7 | needed_prefix = running_sum - k |
| 8 | if needed_prefix in prefix_counts: |
| 9 | total_matches += prefix_counts[needed_prefix] |
| 10 | prefix_counts[running_sum] += 1 |
| 11 | return total_matches |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Negative numbers break the two-pointer sliding window from earlier archetypes entirely — growing the window can now decrease the sum, so "shrink when too big" no longer makes sense. This calls for a completely different mechanism: no pointers at all, just a running total and a memory of totals you've already seen.
🧾 The Analogy: A Running Bank Balance and a Ledger of Past Balances
Imagine tracking your running bank balance day by day, and writing down every balance you've ever had in a ledger, with how many times you've hit each one. Today's question: "was there ever a stretch of consecutive days where I gained exactly k?" That's true exactly when today's balance minus k matches some balance you had on an earlier day — because the days in between are precisely the stretch that gained k. You don't need to re-add up every possible stretch; you just check the ledger for "have I seen (today's balance) - k before?"
🗂️ What the Dictionary (prefix_counts) is Made Of
To make sure you never wonder what the dictionary stores:
- Key: The running sum.
- Value: The number of times we've seen it.
🔑 The Key Idea in the Code
The prefix_counts[0] = 1 seed handles the case where the winning stretch starts from day one — an implicit "balance of 0 before any days have passed."
Forgetting to seed the hash map with
prefix_counts[0] = 1: Ifrunning_sum == kat indexi, thenneeded_prefix = running_sum - k = 0. Without the initialprefix_counts[0] = 1base case recording an implicit sum of 0 before index 0, subarrays starting at index 0 that sum tokare completely missed.Attempting a two-pointer sliding window with negative numbers or zeroes: Sliding window requires monotonicity: expanding must increase (or stay non-decreasing) the sum, and shrinking must decrease it. When array elements can be negative, expanding can decrease the sum and shrinking can increase it, destroying the sliding window invariant. Prefix sum difference with a hash map is required.
Recording
running_sumintoprefix_countsbefore queryingneeded_prefix: Ifk == 0and you insertrunning_sumintoprefix_countsbefore checkingif needed_prefix in prefix_counts, the element matches against its own just-inserted self, counting an invalid empty subarray of length 0.Storing boolean presence in a set instead of frequencies in a dictionary: Because array elements can be zero or negative, the exact same prefix sum can occur multiple times at different indices. A set only remembers that a sum was seen, not how many times. Storing frequencies (Key: The running sum. Value: The number of times we've seen it.) is strictly necessary to count all valid combinations.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Continuous subarray sum condition with negative values or zeros where sliding window is non-monotonic.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: before num is added, prefix_counts holds how often each earlier prefix sum occurred, so the subarrays ending here with sum k number prefix_counts[running_sum - k].
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Using a hash set instead of a frequency map: several earlier prefixes can share the same sum (zeros, or values that cancel out), and each one starts a different subarray, so their counts must be added.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use a Prefix Sum Map. The sum of a subarray is the running sum at its end minus the running sum just before its start. So a subarray ending at the current element sums to k exactly when an earlier running sum equals running_sum minus k. I keep prefix_counts, which says how many times each running sum has appeared, look up running_sum minus k and add that count to the answer, and only then add the current running_sum to the map. Every subarray is counted once, at its last element, and nothing depends on the values being positive, so negative numbers work, where a sliding window would fail. The trap is the empty prefix: I must start with prefix_counts[0] = 1, or every subarray that begins at index 0 is missed; for [1, 1, 1] with k = 2, I would count 1 instead of 2. It's
O(N)time andO(N)space for the map."
Complexity & Mathematical Proof
O(N)
Look at the loop: for num in nums runs N times; each pass does one addition to running_sum, one lookup of needed_prefix in prefix_counts and one insert, all O(1) on average. Total: O(N).
O(N) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. prefix_counts maps each prefix sum seen so far (the key) to how many times it has occurred (the value), holding at most N + 1 distinct keys in the worst case.
T(N) = ∑_{i=1}^N O(1) = O(N)
Derivation Progression
prefix_sum += nums[i]
Computes running sum in O(1) arithmetic per element.
count += prefix_map[Pi - K]
Subarray nums[j..i] sums to K iff - == K, meaning == - K.
prefix_map[Pi] += 1
Records current prefix sum in O(1) amortized hash map operation.
Variable Definitions
Total number of elements in the array
Memory Architecture & Bounds
O(1) Iterative
O(N) Prefix sum frequency hash map
O(1) Total count integer
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "total number of subarrays whose sum equals k", "array may contain negative numbers". Because negative values destroy monotonicity of sliding windows, we utilize Cumulative Prefix Sums with Hash Map frequency counting.
, . time with hash map.
Outside Python the prefix sums need a wide type: with values of size up to , running_sum stays within here, but the same code on larger inputs overflows 32 bits; use 64-bit sums.
Subarray Sum Equals K (LeetCode 560)
You have an array of integers nums and a target integer k. Count how many contiguous, non-empty subarrays of nums add up to exactly k, and return that count.
Worked Examples
nums = [1,1,1], k = 22[1,1] at positions 0-1 and [1,1] at positions 1-2 both sum to 2.nums = [1,2,3], k = 32[1,2] and [3] both sum to 3.⚖️Formal Constraints & Bounds
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
Core Insight
prefix[j] - prefix[i] = k implies prefix[i] = prefix[j] - k. By caching seen prefix sum frequencies in a hash table (Key: The running sum. Value: The number of times we've seen it.) initialized with {0: 1}, we resolve all valid left boundaries in single-pass O(N) time.
Real-World Scenario & Production Applications
Financial ledger auditing and telemetry delta balancing where transaction deltas can be positive or negative.
Subproblems & Recurrence Decomposition3 Phases
Maintain running prefix sum curr_sum and a hash map prefix_counts = {0: 1} tracking frequencies of previously seen prefix sums (Key: The running sum. Value: The number of times we've seen it.).
prefix_counts = {0: 1} # Base state: empty prefix sum = 0
# Key: The running sum.
# Value: The number of times we've seen it.
curr_sum = 0
count = 0Step-by-Step Execution Trace Table
Index i | nums[i] | Running Sum (curr) | Query Needed (curr - k) | Matches in Map | Updated Total Count | Hash Map State {sum: freq} |
|---|---|---|---|---|---|---|
| Init | — | 0 | — | — | 0 | {0: 1} |
0 | 1 | 1 | 1 - 2 = -1 | 0 | 0 | {0: 1, 1: 1} |
1 | -1 | 0 | 0 - 2 = -2 | 0 | 0 | {0: 2, 1: 1} |
2 | 1 | 1 | 1 - 2 = -1 | 0 | 0 | {0: 2, 1: 2} |
3 | 1 | 2 | 2 - 2 = 0 | 2 ([0,3], [2,3]) | 0 + 2 = 2 | {0: 2, 1: 2, 2: 1} |
4 | 1 | 3 | 3 - 2 = 1 | 2 ([1,4], [3,4]) | 2 + 2 = 4 | {0: 2, 1: 2, 2: 1, 3: 1} |
The Math, Step by Step
1. The numbers the code compares
Call the prefix sum at : the total of the first elements of nums. So , because it adds no elements. The subarray from index to index has this total:
The code walks through nums once. After it adds nums[R], the variable running_sum holds . The question for this step is: how many subarrays end at index and have total k?
2. Turning "total equals k" into a lookup
A subarray from to has total k exactly when
The right side is known at step . The code calls it needed_prefix = running_sum - k. So the number of subarrays that end at with total k equals the number of earlier prefix sums , with , that are equal to needed_prefix.
The code keeps those earlier prefix sums in a hash map, prefix_counts. prefix_counts[s] is how many of are equal to . One lookup, prefix_counts[needed_prefix], counts every matching start at once.
3. Why this counts every subarray exactly once
Every subarray has exactly one end index and one start index . The code counts it at step , when running_sum is and the map holds . So each subarray is counted once, at its own end.
The rule comes from subtracting two totals. It does not need the values to be positive. That is why the code works with negative numbers in nums. A sliding window cannot do this: with negative values, a longer window can have a smaller total, so the window cannot decide when to shrink.
4. The two lines whose order matters
The base case prefix_counts[0] = 1. It stores , the empty prefix, before the loop. Without it, subarrays that start at index 0 are never counted. In Example 2, nums = [1,2,3] and k = 3, the subarray [1,2] starts at index 0. Its total is found as . Without the stored , the code returns 1 instead of 2.
Look up first, then store. The code checks needed_prefix before it runs prefix_counts[running_sum] += 1. So at step the map holds only , and every match has . If the code stored first, then k = 0 would match with itself. That match is the empty subarray, which the problem does not count. For nums = [1] and k = 0, the store-first order returns 1, and the correct answer is 0.
5. Example 1 by hand
nums = [1,1,1], k = 2. Before the loop, prefix_counts = {0: 1}.
num | running_sum | needed_prefix | prefix_counts before the lookup | Added to total_matches | total_matches | |
|---|---|---|---|---|---|---|
| 0 | 1 | 1 | {0: 1} | 0 | 0 | |
| 1 | 1 | 2 | {0: 1, 1: 1} | 1 | 1 | |
| 2 | 1 | 3 | {0: 1, 1: 1, 2: 1} | 1 | 2 |
At , the match is , so the subarray is indices 0 to 1. At , the match is , so the subarray is indices 1 to 2. The code returns 2, the expected output.
6. Example 2 by hand
nums = [1,2,3], k = 3. Before the loop, prefix_counts = {0: 1}.
num | running_sum | needed_prefix | prefix_counts before the lookup | Added to total_matches | total_matches | |
|---|---|---|---|---|---|---|
| 0 | 1 | 1 | {0: 1} | 0 | 0 | |
| 1 | 2 | 3 | {0: 1, 1: 1} | 1 | 1 | |
| 2 | 3 | 6 | {0: 1, 1: 1, 3: 1} | 1 | 2 |
At , the match is , which gives [1,2]. At , the match is , which gives [3]. The code returns 2, the expected output.
7. From the formulas to the code
| Formula | In subarraySum |
|---|---|
| is stored once | prefix_counts[0] = 1 |
running_sum += num | |
needed_prefix = running_sum - k | |
count of earlier equal to needed_prefix | total_matches += prefix_counts[needed_prefix] |
| store after the lookup | prefix_counts[running_sum] += 1 |
Each step does one lookup and one store in the hash map, so the whole pass takes time. The map holds at most different prefix sums, so it takes space.
| 1 | prefix_counts = defaultdict(int) |
| 2 | prefix_counts[0] = 1 |
| 3 | running_sum = 0 |
| 4 | total_matches = 0 |
| 5 | for num in nums: |
| 6 | running_sum += num |
| 7 | needed_prefix = running_sum - k |
| 8 | if needed_prefix in prefix_counts: |
| 9 | total_matches += prefix_counts[needed_prefix] |
| 10 | prefix_counts[running_sum] += 1 |
| 11 | return total_matches |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Negative numbers break the two-pointer sliding window from earlier archetypes entirely — growing the window can now decrease the sum, so "shrink when too big" no longer makes sense. This calls for a completely different mechanism: no pointers at all, just a running total and a memory of totals you've already seen.
🧾 The Analogy: A Running Bank Balance and a Ledger of Past Balances
Imagine tracking your running bank balance day by day, and writing down every balance you've ever had in a ledger, with how many times you've hit each one. Today's question: "was there ever a stretch of consecutive days where I gained exactly k?" That's true exactly when today's balance minus k matches some balance you had on an earlier day — because the days in between are precisely the stretch that gained k. You don't need to re-add up every possible stretch; you just check the ledger for "have I seen (today's balance) - k before?"
🗂️ What the Dictionary (prefix_counts) is Made Of
To make sure you never wonder what the dictionary stores:
- Key: The running sum.
- Value: The number of times we've seen it.
🔑 The Key Idea in the Code
The prefix_counts[0] = 1 seed handles the case where the winning stretch starts from day one — an implicit "balance of 0 before any days have passed."
Forgetting to seed the hash map with
prefix_counts[0] = 1: Ifrunning_sum == kat indexi, thenneeded_prefix = running_sum - k = 0. Without the initialprefix_counts[0] = 1base case recording an implicit sum of 0 before index 0, subarrays starting at index 0 that sum tokare completely missed.Attempting a two-pointer sliding window with negative numbers or zeroes: Sliding window requires monotonicity: expanding must increase (or stay non-decreasing) the sum, and shrinking must decrease it. When array elements can be negative, expanding can decrease the sum and shrinking can increase it, destroying the sliding window invariant. Prefix sum difference with a hash map is required.
Recording
running_sumintoprefix_countsbefore queryingneeded_prefix: Ifk == 0and you insertrunning_sumintoprefix_countsbefore checkingif needed_prefix in prefix_counts, the element matches against its own just-inserted self, counting an invalid empty subarray of length 0.Storing boolean presence in a set instead of frequencies in a dictionary: Because array elements can be zero or negative, the exact same prefix sum can occur multiple times at different indices. A set only remembers that a sum was seen, not how many times. Storing frequencies (Key: The running sum. Value: The number of times we've seen it.) is strictly necessary to count all valid combinations.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Continuous subarray sum condition with negative values or zeros where sliding window is non-monotonic.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: before num is added, prefix_counts holds how often each earlier prefix sum occurred, so the subarrays ending here with sum k number prefix_counts[running_sum - k].
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Using a hash set instead of a frequency map: several earlier prefixes can share the same sum (zeros, or values that cancel out), and each one starts a different subarray, so their counts must be added.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use a Prefix Sum Map. The sum of a subarray is the running sum at its end minus the running sum just before its start. So a subarray ending at the current element sums to k exactly when an earlier running sum equals running_sum minus k. I keep prefix_counts, which says how many times each running sum has appeared, look up running_sum minus k and add that count to the answer, and only then add the current running_sum to the map. Every subarray is counted once, at its last element, and nothing depends on the values being positive, so negative numbers work, where a sliding window would fail. The trap is the empty prefix: I must start with prefix_counts[0] = 1, or every subarray that begins at index 0 is missed; for [1, 1, 1] with k = 2, I would count 1 instead of 2. It's
O(N)time andO(N)space for the map."
Complexity & Mathematical Proof
O(N)
Look at the loop: for num in nums runs N times; each pass does one addition to running_sum, one lookup of needed_prefix in prefix_counts and one insert, all O(1) on average. Total: O(N).
O(N) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. prefix_counts maps each prefix sum seen so far (the key) to how many times it has occurred (the value), holding at most N + 1 distinct keys in the worst case.
T(N) = ∑_{i=1}^N O(1) = O(N)
Derivation Progression
prefix_sum += nums[i]
Computes running sum in O(1) arithmetic per element.
count += prefix_map[Pi - K]
Subarray nums[j..i] sums to K iff - == K, meaning == - K.
prefix_map[Pi] += 1
Records current prefix sum in O(1) amortized hash map operation.
Variable Definitions
Total number of elements in the array
Memory Architecture & Bounds
O(1) Iterative
O(N) Prefix sum frequency hash map
O(1) Total count integer
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "total number of subarrays whose sum equals k", "array may contain negative numbers". Because negative values destroy monotonicity of sliding windows, we utilize Cumulative Prefix Sums with Hash Map frequency counting.
, . time with hash map.
Outside Python the prefix sums need a wide type: with values of size up to , running_sum stays within here, but the same code on larger inputs overflows 32 bits; use 64-bit sums.