Subarray Sum Equals K — Why Prefix Sum + HashMap Beats Everything [LC 560]

Problem Statement

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals k. A subarray is a contiguous, non-empty sequence of elements within an array.

Constraints: -1000 <= nums[i] <= 1000, so negative numbers are allowed.

Example 1:

Input:  nums = [1, 1, 1], k = 2
Output: 2
Explanation: [1,1] at indices (0,1) and (1,2) both sum to 2.

Example 2 (negative numbers — the tricky case):

Input:  nums = [1, -1, 1], k = 1
Output: 3
Explanation: [1] at index 0, [1,-1,1] at indices (0,2), and [1] at index 2.

• Why This Problem Matters
• Why Sliding Window Fails Here
• Building The Prefix Sum Insight
• The HashMap Trick
• Visual Dry Run
• Example 1: nums = [1, 1, 1], k = 2
• Example 2: nums = [1, -1, 1], k = 1
• Common Mistakes
• Solutions
• Brute Force — O(n²) time, O(1) space
• Optimal — O(n) time, O(n) space (Prefix Sum + HashMap)
• Complexity Analysis
• Follow-up Questions
• This Pattern Solves
• Key Takeaway

Why This Problem Matters

LeetCode 560 is one of the most consistently appearing array problems in FAANG loops — Google, Meta, Amazon, and Microsoft all pull from it or its direct variants. But its value in an interview goes far beyond memorizing a solution. The real reason interviewers love it is because it cleanly separates candidates who understand why a technique works from those who have only seen the answer before.

The prefix sum + hashmap pattern is a fundamental primitive in competitive programming and industry coding. Once you internalize it here, you immediately unlock:

• Subarrays with sum divisible by k (LC 974)
• Binary subarrays with sum (LC 930)
• Subarrays with at most k odd numbers
• Longest subarray with sum k (variant)
• Count subarrays with exactly k distinct characters

All of these problems are structurally identical: they transform a "does this subarray satisfy condition X?" question into a "have I seen a specific prefix value before?" lookup. That lookup is O(1) with a hashmap, making the whole solution O(n).

The prefix sum + hashmap pattern is worth studying deeply — not just for this one problem.

Why Sliding Window Fails Here

Before explaining the correct approach, let's kill the most common wrong instinct first. Many candidates see "subarray sum equals k" and immediately reach for a two-pointer or sliding window. That is the wrong move here, and understanding exactly why is one of the most valuable teaching moments in DSA.

Sliding window works by maintaining a running sum over a contiguous window. When the sum exceeds a target, you shrink from the left; when it falls short, you expand to the right. This logic rests on one critical assumption: adding an element always increases the sum, and removing one always decreases it. In other words, all elements must be positive (or zero) for the window to behave predictably.

The moment you introduce negative numbers, that assumption collapses. Consider this example:

nums = [3, 4, -7, 3, 1, 3, 1, -4, 1, 3], k = 7

Suppose your window has sum 8 (greater than 7), so you shrink from the left by removing 3, getting sum 5. But now sum is less than 7, so you need to expand again. You've created an infinite loop of contradictory moves — the window has no stable direction to travel.

There is no systematic way to decide "shrink" vs. "expand" when the answer is not monotonically related to window size. Trying to patch sliding window for negative numbers leads to exponential edge cases. The sliding window simply does not apply.

The concrete failure on Example 2: For [1, -1, 1], k = 1, sliding window would find [1] at index 0, then see [1, -1] (sum = 0), shrink to [-1] (sum = -1), and lose track. It would never count the full subarray [1, -1, 1] with sum 1. The correct answer is 3; sliding window gives the wrong count.

The fix is not to improve sliding window — it is to use a completely different mental model.

Building The Prefix Sum Insight

Let's define the prefix sum array clearly. Given nums of length n:

prefix[0] = 0
prefix[1] = nums[0]
prefix[2] = nums[0] + nums[1]
prefix[i] = nums[0] + nums[1] + ... + nums[i-1]

The sum of nums[i..j] (the subarray from index i to j inclusive) is:

sum(i, j) = prefix[j+1] - prefix[i]

This is the foundational identity. It converts "sum of a subarray" into "difference of two prefix sums" — and that reframing is everything.

We want sum(i, j) = k, which means:

prefix[j+1] - prefix[i] = k
=> prefix[i] = prefix[j+1] - k

So instead of checking all pairs (i, j) in O(n²), we can ask a smarter question: as we compute prefix[j+1], have we ever seen the value prefix[j+1] - k before?

If yes, every time we saw it corresponds to a valid starting index for a subarray ending at j. We just need to count those occurrences.

Let's trace through nums = [1, 2, 3], k = 3:

prefix values (computed as we scan):
After index 0: prefix = 1. Looking for 1 - 3 = -2. Not seen. Store {0:1, 1:1}
After index 1: prefix = 3. Looking for 3 - 3 = 0. Seen once! count += 1. Store {..., 3:1}
After index 2: prefix = 6. Looking for 6 - 3 = 3. Seen once! count += 1. Store {..., 6:1}
Total: 2

The subarrays are [1,2]... wait, actually [3] (index 2) and [1,2] (indices 0–1) — both sum to 3. Correct.

The HashMap Trick

Here's the critical realization: we don't need to store the entire prefix sum array. We only ever need to know "how many times has prefix value X appeared so far?" — which is exactly what a hashmap gives us.

We maintain a single dictionary count that maps {prefix_sum → number_of_times_seen}. We update it as we move through the array from left to right.

Why initialize with {0: 1}?

This handles subarrays that start from index 0. If prefix[j+1] = k exactly, we need prefix[i] = 0, which corresponds to the "empty prefix" before the array starts. Without {0: 1}, we would miss all subarrays that begin at index 0 and sum exactly to k. This is the single most common bug in implementations of this pattern.

Here is the complete algorithm:

Initialize: count = {0: 1}, prefix = 0, result = 0

For each num in nums:
    prefix += num                          # extend the prefix sum
    result += count.get(prefix - k, 0)    # check if complement exists
    count[prefix] += 1                     # record this prefix sum

Notice the order of operations: we check prefix - k before adding prefix to the map. This prevents a subarray from counting itself (matching prefix[i] with prefix[i] at the same index).

Visual Dry Run

Example 1: nums = [1, 1, 1], k = 2

Output: 2 — correct. The subarrays are [1,1] at (0,1) and [1,1] at (1,2).

Example 2: nums = [1, -1, 1], k = 1

Output: 3 — correct. The three subarrays are [1] (index 0), [1, -1, 1] (indices 0–2), and [1] (index 2).

Notice how at i=2, the target is 0 and its count is 2. This accounts for two distinct starting points: the empty prefix (giving the subarray starting at index 0) and the prefix after index 1 (giving the subarray starting at index 2). A sliding window could never discover these simultaneously.

Common Mistakes

Mistake 1: Forgetting {0: 1} initialization. This causes you to miss all subarrays starting from index 0. If the first few elements sum to k, the algorithm finds prefix - k = 0 in the map but counts 0 occurrences instead of 1. Always seed the hashmap with the empty-prefix entry.

Mistake 2: Using sliding window on inputs with negative numbers. This is the most conceptually damaging mistake. If an interviewer says "the array may contain negative integers," sliding window is immediately eliminated. Recognize this constraint and pivot to prefix sum + hashmap immediately.

Mistake 3: Adding to the map before checking the target. If you do count[prefix] += 1 and then check count.get(prefix - k), you may count a subarray that starts and ends at the same position (when k = 0). Always check the complement first, then update the map.

Mistake 4: Returning True/False instead of counting occurrences. The hashmap must store counts, not just presence. A prefix sum can appear multiple times (as in Example 2 above where prefix 0 appeared twice). Using a set instead of a counter underestimates the answer.

Solutions

Brute Force — O(n²) time, O(1) space

Good to mention as a baseline. For every pair (i, j), compute the sum and check if it equals k.

Python:

def subarraySum(nums: list[int], k: int) -> int:
    count = 0
    n = len(nums)
    for i in range(n):
        total = 0
        for j in range(i, n):
            total += nums[j]      # extend window from i to j
            if total == k:
                count += 1
    return count

JavaScript:

function subarraySum(nums, k) {
    let count = 0;
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        let total = 0;
        for (let j = i; j < n; j++) {
            total += nums[j];     // extend window from i to j
            if (total === k) count++;
        }
    }
    return count;
}

Optimal — O(n) time, O(n) space (Prefix Sum + HashMap)

Python:

from collections import defaultdict

def subarraySum(nums: list[int], k: int) -> int:
    # Maps prefix_sum -> number of times it has been seen
    count = defaultdict(int)
    count[0] = 1          # empty prefix: sum 0 has been seen once

    prefix = 0
    result = 0

    for num in nums:
        prefix += num             # update running prefix sum

        # If (prefix - k) was seen before, those positions are valid
        # left endpoints of subarrays ending here with sum k
        result += count[prefix - k]

        # Record the current prefix sum for future iterations
        count[prefix] += 1

    return result

JavaScript:

function subarraySum(nums, k) {
    // Maps prefix_sum -> number of times it has been seen
    const count = new Map();
    count.set(0, 1);   // empty prefix: sum 0 has been seen once

    let prefix = 0;
    let result = 0;

    for (const num of nums) {
        prefix += num;               // update running prefix sum

        // If (prefix - k) was seen before, those positions are valid
        // left endpoints of subarrays ending here with sum k
        result += (count.get(prefix - k) || 0);

        // Record the current prefix sum for future iterations
        count.set(prefix, (count.get(prefix) || 0) + 1);
    }

    return result;
}

Complexity Analysis

The hashmap stores at most one entry per unique prefix sum value. In the worst case (all prefix sums distinct), that is O(n) entries. Each lookup and insert is O(1) on average. The single pass through the array makes the overall time O(n).

Follow-up Questions

These are direct extensions interviewers ask after you solve LC 560:

1. Subarray Sums Divisible by K (LC 974) Instead of sum == k, we want sum % k == 0. The prefix sum identity still holds, but we replace raw prefix sums with their remainder modulo k. Two prefix positions i and j give a sum divisible by k if and only if prefix[j] % k == prefix[i] % k. Use a hashmap counting {remainder: frequency} with initial entry {0: 1}. Watch out: Python's % always returns non-negative; in other languages you may need ((prefix % k) + k) % k to avoid negative remainders.

2. Binary Subarrays With Sum (LC 930) The array contains only 0s and 1s; count subarrays with sum exactly goal. This is the "exactly k = at most k minus at most (k-1)" trick: exactlyK(nums, goal) = atMostK(nums, goal) - atMostK(nums, goal - 1). The atMostK function uses a standard sliding window because values are non-negative (0 and 1 only). This decomposition is powerful — it converts an "exactly" problem into two "at most" problems.

3. Subarrays With at Most K Odd Numbers Use a sliding window counting odd numbers in the current window. Because we only add 0 or 1 to the count (not arbitrary values), the window remains monotonic and shrinking is well-defined. This contrasts with the original problem: here values are restricted so sliding window works again.

4. Longest Subarray With Sum K Same prefix sum setup, but instead of counting occurrences, store the first time each prefix sum appears ({prefix: index}). When you find prefix - k in the map, the subarray length is current_index - map[prefix - k]. Do not update the map if the prefix sum already exists — you want the earliest index.

This Pattern Solves

The prefix sum + hashmap pattern applies any time the problem involves:

• Contiguous subarrays
• A sum, count, balance, or modular condition
• The ability to express the condition as prefix[j] - prefix[i] = target

Problems that use the same backbone: LC 525 (Contiguous Array), LC 1124 (Longest Well-Performing Interval), LC 437 (Path Sum III — on trees), LC 523 (Continuous Subarray Sum), and LC 1248 (Count Number of Nice Subarrays).

Once you internalize the pattern, you stop solving individual problems and start recognizing a problem family. That is the goal of studying DSA at this level.

Key Takeaway

The prefix sum + hashmap pattern converts "does a subarray from index i to j satisfy condition X?" into a single-pass O(n) lookup problem by reframing it as "have I seen the complementary prefix value before?" The {0: 1} initialization is not a trick — it is the mathematically correct way to account for the empty prefix, and forgetting it is the most common source of wrong answers. Sliding window cannot replace this approach when negative numbers are present because it relies on monotonicity that does not hold. Master this pattern and you unlock an entire family of FAANG-grade problems.