DSA sheet · Arrays · Prefix Sum pattern

Subarray Sum Equals K

This is the first question of the Prefix Sum pattern, and the teacher spends two videos on it. In Part 1 she writes the brute force (two loops), reads the constraints, rules out the other array patterns one by one, and then writes the prefix sum + hashmap solution. In Part 2 she comes back only to build the intuition slowly: why a plain prefix sum array is not enough, why we need a map of counts, and why the map starts with {0: 1}.

Why it matters: "count subarrays whose sum is exactly k" is a pattern you will see again and again (count subarrays divisible by k, binary subarrays with sum, nice subarrays…). The same trick of "remember how many times each prefix sum has appeared" solves all of them.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (prefix sum, hashmap of counts)
• Part A · Brute force: try every subarray (video 1)
• Part B · Optimal: prefix sum + hashmap of counts (videos 1 & 2)
• Part C · Revision page

Part 0 · Before starting

What is a subarray?

A subarray is a piece of the array where the elements sit next to each other (contiguous). You choose a start index l and an end index r (with l ≤ r) and take everything between them. You can't skip elements in the middle.

An array of length n has n·(n+1)/2 non-empty subarrays. For n = 4 that's 10.

What is a prefix sum?

A prefix is the start of the array: everything from index 0 up to some index i. The prefix sum at i is the total of that start part:

prefix[i] = nums[0] + nums[1] + … + nums[i]

We don't add everything again for every i. Each cell is just the cell before it plus one new number:

prefix[0] = nums[0]  and  prefix[i] = prefix[i-1] + nums[i]

The teacher builds it on the same array she uses for the whole problem:

Why sum(l..r) = prefix[r] − prefix[l−1]

Both prefixes start at index 0. The longer one, prefix[r], covers 0…r. The shorter one, prefix[l−1], covers 0…l−1. If you take the long one and remove the short one, only the piece l…r is left. The teacher says it as "bigger one minus smaller one".

  prefix[r]    = |  0 ........ l-1  |  l ........ r  |
  prefix[l-1]  = |  0 ........ l-1  |
  difference   =                    |  l ........ r  |   = sum(l..r)

Her example: what is the sum of nums[1..3] = (−1, 0, 1)?

prefix[3] is 1 − 1 + 0 + 1 = 1. prefix[0] is 1. The difference is 0, and indeed −1 + 0 + 1 = 0 ✓. One subtraction instead of a loop.

The "−1" problem and the empty prefix = 0 trick

What if l = 0? Then we need prefix[−1], which doesn't exist. But think about what it means: "the sum of the elements before index 0". There are none, so it's the sum of an empty prefix, which is 0. So:

• sum(0..r) = prefix[r] − 0 = prefix[r]. For example, sum(0..4) = 3.
• A common way to code it is to shift the array by one: keep P[0] = 0 for the empty prefix and P[i+1] = P[i] + nums[i]. Then sum(l..r) = P[r+1] − P[l], and there's no special case.

def build_prefix(nums):
    P = [0] * (len(nums) + 1)          # P[0] = 0 is the empty prefix
    for i in range(len(nums)):
        P[i + 1] = P[i] + nums[i]      # previous total + one new number
    return P

def range_sum(P, l, r):
    return P[r + 1] - P[l]             # (0..r) minus (0..l-1)

What a prefix sum array alone is good for, and what it is NOT good for

The teacher makes this point in Part 2. A prefix array answers "what is the sum from l to r?" in O(1), and that's great when the question gives you many (l, r) queries, or asks a yes/no question. But here the question is "how many subarrays have sum k?" We don't know l and r; we'd have to try every pair, which brings back O(n²). For counting, she adds a frequency map.

What is a hashmap (dict) of counts?

A Python dict stores key → value pairs, and looking up a key takes O(1) on average. A frequency map (or count map) uses the thing we have seen as the key and how many times we've seen it as the value.

freq = {}
for x in [5, 2, 5, 5]:
    freq[x] = freq.get(x, 0) + 1     # {5: 3, 2: 1}

freq.get(x, 0) means "the count of x, or 0 if x isn't there yet". It's the same as Java's getOrDefault, which the teacher uses.

The 4 array patterns the teacher always checks

Whenever she wants to optimise an array problem, she goes through the four patterns from the first video of the playlist and asks which one fits:

Part A · Brute force: try every subarray

LeetCode 560 · from video 1

1The question in simple words

You get an array of integers nums and an integer k. Return how many subarrays have a sum of exactly k.

Two things to notice. First, it asks for a count, not True/False and not the subarrays themselves. Second, it says exactly k, not "at most k". Both details decide which pattern we can use later.

The 4 subarrays with sum 3 are:

• index 0..4: 1 − 1 + 0 + 1 + 2 = 3
• index 2..4: 0 + 1 + 2 = 3
• index 3..4: 1 + 2 = 3
• index 6..6: just 3

LeetCode's small examples: [1,1,1], k=2 → 2 and [1,2,3], k=3 → 2 ([1,2] and [3]).

2What the constraints tell us

• 1 ≤ n ≤ 2·10⁴. O(n) is 2·10⁴ steps. O(n²) is 4·10⁸ steps. The teacher's rule: beyond about 10⁸ operations you risk TLE, or at least a very slow solution. So we will need to optimise, but she still writes the brute force first.
• −1000 ≤ nums[i] ≤ 1000, so numbers can be negative. She asks us to remember this, because it is what decides the pattern later (it kills sliding window).
• −10⁷ ≤ k ≤ 10⁷. k can also be negative, zero or positive. An int holds up to about 10⁹, so storing k is fine. (The largest possible prefix sum is 2·10⁴ × 1000 = 2·10⁷, also fine. Python ints never overflow anyway.)
• n ≥ 1, so the array is never empty.

3Intuition: list every subarray and add it up

The simplest idea: if we could go through every subarray, add up its numbers and check whether the total is k, we just do count += 1 each time it is.

Picture it as two fingers. The left finger marks where the subarray starts. The right finger starts at the same place and walks to the end, one step at a time. Each position of the right finger is one subarray l..r. When the right finger reaches the end, the left finger moves one step and the right finger starts again from there.

4Building the logic from the example

Start the left finger at index 0

We keep a running sum for the current start. Each time the right finger moves, we add the one new number. We don't re-add the whole subarray.

Starting at index 0 we found exactly one valid subarray.

Move the left finger to index 1

The running sum must start from 0 again, because this is a new subarray family. Right finger from 1: −1, −1, 0, 2, 1, 4. None of them is 3 → no valid subarray starting at index 1.

And so on for every left position

Doing this for every start gives one subarray from start 0, one from start 2 (0,1,2), one from start 3 (1,2) and one from start 6 (just 3). Total 4. Notice: we never printed the subarrays. The question only wants the count, so a counter is enough.

5Approach steps

1. count = 0.
2. For each start l from 0 to n−1: set s = 0.
3. For each end r from l to n−1: add nums[r] to s.
4. If s == k, do count += 1.
5. After both loops, return count.

6Code (Python)

class Solution:
    def subarraySum(self, nums, k):
        n = len(nums)
        count = 0
        for l in range(n):               # where the subarray starts
            s = 0                        # fresh sum for this start
            for r in range(l, n):        # where it ends
                s += nums[r]             # sum of nums[l..r]
                if s == k:
                    count += 1
        return count

7Code line by line

8Dry run (hand table)

nums = [1, −1, 0, 1, 2, −1, 3], k = 3. Each row is one start l. The running sums are listed in order as r moves right; ✓ marks a hit.

Final answer: 4 ✓, the same four subarrays we listed in step 1.

9Complexity & remember

• Time O(n²): for every l, the inner loop runs up to n times. With n = 2·10⁴ that's up to about 2·10⁸ additions (n²/2), right at the danger line.
• Space O(1): only a few variables.

The teacher submitted it and it was accepted but very slow. That is her signal to look for a better pattern.

Part B · Optimal: prefix sum + hashmap of counts

LeetCode 560 · code from video 1, intuition from video 2

1The question again, with the new goal

Same question: count the subarrays with sum exactly k. The new goal is to do it in one pass (one loop, O(n)) instead of two nested loops.

2What the constraints tell us now

• n up to 2·10⁴ → O(n²) is too slow, so we want O(n) (or O(n log n)).
• nums[i] can be negative → this decides the pattern (next step).
• k can be negative or 0 → our method must not assume k > 0.

3Choosing the pattern: why the other three fail

The teacher goes through her four patterns and rules out three of them, giving a reason for each. This reasoning is what interviewers want to hear.

✗ Two pointers

Two pointers is for questions where only the two end points matter and nothing in between (and, as she adds in video 2, usually when the array is sorted). Here we need the sum of everything between l and r, and the array isn't sorted. So two pointers is out.

✗ Sliding window

Sliding window also works on contiguous sums, but it has one rule: it works only when the numbers are positive. Once a negative number can be inside the window, it breaks. Here's why. Sliding window decides with two moves:

• sum too small → grow the window (move right), because adding should make it bigger;
• sum too big → shrink the window (move left), because removing should make it smaller.

With negatives, both promises are false: adding a negative makes the sum smaller, and removing a negative makes it bigger. The window moves the wrong way and skips answers. A small example (my own, to show her point):

1. Window [2] → sum 2 = k → count 1.
2. Grow: [2, −1] → sum 1, too small → grow.
3. Grow: [2, −1, 2] → sum 3, too big → shrink from the left: [−1, 2] → sum 1, now too small → stop shrinking.
4. The right end is at the last index → done. Count = 1. Wrong. The window never looked at [2] alone at index 2, because it stopped shrinking when the sum dropped to 1. It had no way to know that removing the −1 would push the sum back up to 2.

✗ Kadane's algorithm

Kadane's does handle negatives, but it answers a different question: the maximum subarray sum. It keeps one best value. It can't tell you how many subarrays hit an exact total. So it's out too.

✗ The "right − left + 1" counting trick

In earlier sliding-window problems, the teacher counted subarrays by adding right − left + 1 for each window. She explains why that doesn't work here: that trick counts subarrays with sum at most k (≤ k), and only for positive numbers. Here we need exactly k, and there are negatives.

4Building the idea from examples (the intuition from video 2)

Step 1: a single running sum is a prefix sum

Walk through the array once with one pointer and keep a running total s. At index i, s is the sum of everything from 0 to i, so s is prefix[i]. We don't need to store a prefix array. The variable s holds the current prefix, and the map will remember the old ones.

On our array, s goes: 1, 0, 0, 1, 3, 2, 5. At index 4, s = 3 = k. That tells us subarray 0..4 is valid. But how many valid subarrays end at index 4? A single "s == k?" check only finds subarrays that start at 0. We'd miss 2..4 and 3..4.

Step 2: the "leftover" picture

Fix the end at index i. Any subarray that ends at i looks like this: the whole prefix (0..i) is split into a front part (0..j−1) and the subarray (j..i):

  0 ............ j-1 | j ............ i
 |----- front -------|---- subarray ---|
 |------------ s = prefix[i] ----------|

  subarray sum = s - (front sum)
  we want it = k   →   front sum must be  s - k

So asking "which subarrays ending at i sum to k?" is the same as asking "how many earlier prefixes had sum exactly s − k?" Each such earlier prefix is a different place to cut, and each cut leaves a different subarray with sum k.

The teacher calls s − k the remaining or leftover part. She stores it in a variable named target: target = prefixSum − k.

Step 3: why the map stores COUNTS, not just "seen / not seen"

On our array at index 4, s = 3, so target = 3 − 3 = 0. Which earlier prefixes had sum 0? Let's list them:

Prefix sum 0 has appeared 3 times (counting the empty prefix before index 0). Each one gives a cut:

Three cuts → three subarrays ending at index 4. That's why a set ("have I seen 0?") is not enough. We need how many times each prefix sum appeared. The teacher's way to say it: however many times the front part (sum 0) has occurred, the leftover part (sum 3) has occurred the same number of times, because together they always make the full sum 3.

Step 4: why map[0] = 1 at the start (her "aha" moment in video 1)

In video 1, the teacher first fills the map without anything in it at the start. Watch what happens at index 4:

It finds only 2 subarrays ending at index 4 (2..4 and 3..4), but there are 3. The missing one is the whole prefix 0..4, the subarray that starts at index 0. Its front part is the empty prefix, whose sum is 0, and we never recorded it.

An even simpler case she gives: nums = [3], k = 3. s = 3, target = 0, and the map is empty → answer 0. Wrong, since [3] itself is valid.

The fix: put the empty prefix in the map before the loop: freq = {0: 1}. It means "a prefix with sum 0 has been seen once: the empty one, before index 0". Now at index 4 the count of 0 is 3, and for [3] the lookup of 0 finds 1 ✓.

Step 5: look up first, then add the current prefix

At each index we do two things, in this order:

1. Look up s − k and add its count to the answer.
2. Record the current s in the map: freq[s] = freq.get(s, 0) + 1.

5Approach steps

1. freq = {0: 1}: the empty prefix has been seen once.
2. s = 0 (running prefix sum), count = 0.
3. For each number x in nums: s += x.
4. target = s − k. If target is in freq, add freq[target] to count. That's the number of subarrays ending here with sum k.
5. Record the current prefix: freq[s] = freq.get(s, 0) + 1 (always).
6. After the loop, return count.

6Code (Python)

class Solution:
    def subarraySum(self, nums, k):
        freq = {0: 1}          # empty prefix: sum 0 seen once
        prefix_sum = 0
        count = 0
        for x in nums:                     # one pass, like her for-each loop
            prefix_sum += x                # sum of nums[0..i]
            target = prefix_sum - k        # the front part we need
            if target in freq:
                count += freq[target]      # one subarray per earlier cut
            freq[prefix_sum] = freq.get(prefix_sum, 0) + 1   # always record
        return count

Shorter way, same meaning: replace the if with count += freq.get(prefix_sum - k, 0). Some people use collections.defaultdict(int) for freq. Both work the same.

7Code line by line

8Dry run (hand table, the map grows step by step)

nums = [1, −1, 0, 1, 2, −1, 3], k = 3. Start: freq = {0:1}, prefix_sum = 0, count = 0.

The same steps as a story, the way she narrates it:

1. i=0: sum 1. Need −2? Not there. Record 1 → {0:1, 1:1}.
2. i=1: sum 0. Need −3? No. 0 is already in the map, so its count goes to 2.
3. i=2: sum still 0. Need −3? No. 0 goes up to 3. "Zero has now appeared three times."
4. i=3: sum 1. Need −2? No. 1 goes up to 2.
5. i=4: sum 3. Don't think "sum is 3, so that's one answer". Look up 3 − 3 = 0 → it appeared 3 times → three subarrays end here: [1,−1,0,1,2], [0,1,2], [1,2]. count = 3. Record 3.
6. i=5: sum 2. Need −1? No. Record 2.
7. i=6: sum 5. Need 5 − 3 = 2 → it appeared once (the prefix up to index 5). The front part 1,−1,0,1,2,−1 sums to 2, so the leftover [3] sums to 3. count = 4. Record 5.
8. Loop ends → return 4 ✓, the same answer as the brute force.

9Complexity & remember

• Time O(n): one loop, and inside it only O(1) dict operations (look up, insert). No inner pointer.
• Space O(n): in the worst case every prefix sum is different, so the map holds up to n + 1 keys.

She submitted it and it beat about 94% of solutions, far faster than the brute force. A small trade: we spend O(n) memory to save a whole loop.

Part C · Revision page

s = Solution()
print(s.subarraySum([1, -1, 0, 1, 2, -1, 3], 3))   # 4
print(s.subarraySum([1, 1, 1], 2))                 # 2
print(s.subarraySum([1, 2, 3], 3))                 # 2
print(s.subarraySum([3], 3))                       # 1  (needs {0: 1})
print(s.subarraySum([0, 0, 0], 0))                 # 6
print(s.subarraySum([2, -1, 2], 2))                # 2  (sliding window says 1)

Based on these videos: Subarray Sum Equals K · Part 1 (brute force → prefix sum) · Subarray Sum Equals K · Part 2 (prefix sum + hashmap intuition)