Subarray Sum Equals K

Hints

1. Start with the obvious. Two nested loops, summing each (l, r) slice. Make this work first; correctness before speed.
2. Spot the redundant work. The brute force computes overlapping sums. Can you precompute prefix sums so that the sum of any slice is one subtraction?
3. Reframe the question. A subarray nums[l..r) sums to k exactly when P[r] − P[l] = k, i.e. P[l] = P[r] − k. So the problem becomes "for each r, how many earlier l have prefix sum equal to P[r] − k?"
4. Which data structure answers "how many previous values equal X?" in O(1)? A hash map keyed by prefix sum, valued by count. This is the same seen-so-far pattern as Two Sum, applied to prefix sums.
5. Don't forget the empty prefix. Seed the hash map with {0: 1} before the loop. This represents the prefix sum P[0] = 0 and is what counts subarrays that start at index 0.
6. Order: query, then insert. If you insert first, an element with value k would match itself at the same prefix-sum position. Querying before inserting prevents this.

Solution: three approaches

Approach 1 · Brute force: O(n²) time, O(1) space

Two nested loops. The outer fixes the start l; the inner extends r and accumulates the sum, comparing to k at each step. Correct, but quadratic.

def subarray_sum_brute(nums, k):
    count = 0
    for l in range(len(nums)):
        s = 0
        for r in range(l, len(nums)):
            s += nums[r]
            if s == k:
                count += 1
    return count

Why this is the right starting point: it builds the right mental model. We're enumerating subarrays and asking a question about each. The inefficiency is that we recompute overlapping prefix sums. The inner loop's running total s is exactly a slice of the prefix sum, but we throw it away when l advances.

Approach 2 · Prefix sums: O(n²) time, O(n) space

Halfway step. Precompute the prefix sum array, then for each pair (l, r) compute the slice sum as a single subtraction. Same complexity as brute force on the count of pairs, but each pair is now O(1). Useful as a reasoning bridge to Approach 3.

def subarray_sum_prefix(nums, k):
    n = len(nums)
    P = [0] * (n + 1)
    for i, x in enumerate(nums):
        P[i + 1] = P[i] + x
    count = 0
    for l in range(n + 1):
        for r in range(l + 1, n + 1):
            if P[r] - P[l] == k:
                count += 1
    return count

The key insight surfaces here: every valid subarray corresponds to a pair of prefix-sum values that differ by exactly k. So the problem is: "how many ordered pairs (P[l], P[r]) with l < r have P[r] − P[l] = k?"

Approach 3 · Prefix sums + hash map: O(n) time, O(n) space

This is the canonical solution. Walk through the prefix sums one at a time. At each r, ask "how many earlier l had P[l] = P[r] − k?" That's a single hash-map lookup. Then record the current prefix sum.

from collections import defaultdict

def subarray_sum(nums, k):
    seen = defaultdict(int)
    seen[0] = 1                       # the empty prefix; counts subarrays starting at index 0
    running = 0
    count = 0
    for x in nums:
        running += x
        count += seen[running - k]    # query first
        seen[running] += 1            # then insert
    return count

Why seen[0] = 1: the empty prefix represents P[0], the sum before we've consumed any elements. If a subarray starts at index 0 and has sum exactly k, then at the moment we reach the end of that subarray, running = k, and we look up seen[k − k] = seen[0], which must be 1 for that subarray to be counted. Forgetting this seed is the most common bug; it silently undercounts in exactly the cases readers find hardest to debug.

Why query before insert: consider nums = [3], k = 0. After processing the single element, running = 3. If we inserted first, seen = {0: 1, 3: 1}, then queried seen[3 − 0] = seen[3] = 1, falsely counting an empty subarray. Querying first prevents an element from pairing with itself.

Why defaultdict(int): the lookup seen[running - k] happens regardless of whether the key exists. With a plain dict you'd need .get(running - k, 0); defaultdict makes the missing-key case implicit and the code one line shorter.

Complexity comparison

Edge cases to verify

• Single element equals k: nums=[5], k=5 → 1. The seed seen[0]=1 matches the running total of 5 against 5 − 5 = 0.
• k = 0 with zeroes in the array: nums=[0,0,0], k=0 → 6. Each pair of indices forms a zero-sum subarray; the hash map quickly accumulates large counts.
• Negative numbers: nums=[1,-1,1], k=0 → 2. The prefix-sum approach handles negatives without modification; there's no monotonicity assumption.
• No matches: nums=[1,2,3], k=100 → 0. The map fills with prefix sums, but no running − k key is ever found.
• Whole array equals k: nums=[1,2,3], k=6 → 1. At the end, running = 6, and we look up seen[0] which is 1 (the seed).

Where beginners go wrong

• Forgetting the empty-prefix seed. Initialising seen = {} instead of seen = {0: 1} silently undercounts every subarray that starts at index 0. The bug is hard to spot because most test inputs avoid it; it shows up specifically when the answer includes a subarray beginning at the very start of the array.
• Inserting before querying. Produces wrong answers when k = 0 with zeroes in the array, or whenever an element exactly matches a previously-seen prefix value. The order is: look up the complement, then record yourself.
• Confusing "subarray sum" with "subset sum". Subarrays must be contiguous; subsets can pick any elements. The two problems have very different complexities: subset sum is NP-hard in general; subarray sum is O(n) with this technique.
• Using a list instead of a hash map. Looking up running − k in a list is O(n); inside the loop it makes the algorithm O(n²), back to brute-force complexity. The hash map is what makes the technique linear.
• Two-pointer attempt. The two-pointer / sliding-window technique works only when partial sums are monotone in the window size, typically with non-negative values. With negatives in nums, expanding the window can decrease the sum, breaking the invariant. Prefix sums plus hash map is the right tool when negatives are allowed.

Interview follow-ups to expect

• "What if you needed the longest such subarray, not the count?" Store the earliest index where each prefix-sum value first appears: seen[P[r]] = r (insert only if absent). At each r, the longest valid subarray ending at r has length r − seen[P[r] − k]. The earliest-index insertion rule maximises that length.
• "What if the array allowed updates?" Prefix sums become invalid the moment any element changes. Reach for a Fenwick tree (Binary Indexed Tree) for O(log n) point updates and range-sum queries.
• "Make it work in 2D: count submatrices summing to k." Fix the top and bottom row pair, collapse the strip into a 1D array of column sums, run the 1D algorithm. O(rows² × cols) total. The 1D core is exactly this problem.
• "What about a streaming version where elements arrive one at a time?" The algorithm above already works in a streaming way: each element is processed in O(1) and the hash map can grow incrementally. The full array doesn't need to fit in memory, only the distinct prefix sums.

Related reading

• Prefix Sums in Practice, the deep-dive that this problem exercises.
• Hash Maps & Sets, where the seen-so-far pattern is formalised.
• Two Sum, the same pattern applied to values instead of prefix sums.