Subarray Sum Equals K — Prefix Sums and the Complement Map

Problem Statement#

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

Constraints:

• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

Example 1:
Input:  nums = [1, 1, 1], k = 2
Output: 2
Explanation: [1,1] appears at positions [0,1] and [1,2].

Example 2:
Input:  nums = [1, 2, 3], k = 3
Output: 2
Explanation: [1,2] and [3] both sum to 3.

Example 3:
Input:  nums = [1, -1, 1, -1], k = 0
Output: 4
Explanation: Subarrays: [1,-1], [-1,1], [1,-1], and [1,-1,1,-1].

Why This Problem Matters#

Subarray Sum Equals K is one of the most important medium problems you will encounter in FAANG interviews. It combines two foundational techniques — prefix sums and hash map complement lookup — into a single elegant algorithm. Amazon asks this in nearly every data engineering interview loop; Google uses it as a filter for candidates who understand the difference between O(n^2) and O(n) subarray sum solutions.

The problem is significant because it cannot be solved with a sliding window (negative numbers allow the sum to decrease even as the window expands), yet it has a clean O(n) solution using the prefix sum trick. Many candidates who have memorized sliding window patterns get stuck here because the obvious "shrink the window when the sum is too large" approach fails for arrays with negative numbers.

The prefix sum hash map pattern is broadly applicable: it appears in Continuous Subarray Sum (check if any subarray sums to a multiple of k), Maximum Size Subarray Sum Equals k (find the longest such subarray), Binary Subarray With Sum (count subarrays with exactly k ones), and many other variants. Each of these is a slight variation of the same underlying idea.

Understanding this pattern deeply means understanding the mathematical relationship: if prefix[j] - prefix[i] = k, then the subarray from index i+1 to j has sum k. Rearranging: prefix[i] = prefix[j] - k. So for each j, count how many previous prefix sums equal prefix[j] - k. That count is the number of valid subarrays ending at j.

The Core Insight#

Define prefix[j] = sum of nums[0..j] (the prefix sum up to index j). The sum of subarray nums[i..j] is prefix[j] - prefix[i-1].

If prefix[j] - prefix[i-1] == k, then prefix[i-1] == prefix[j] - k.

So for each position j, we want to count how many previous positions i-1 have prefix[i-1] == prefix[j] - k. This is a direct hash map lookup.

Algorithm:

1. Initialize a hash map count with {0: 1} — the empty prefix (before index 0) has sum 0, and it counts once.
2. Maintain a running prefix sum running.
3. For each element in nums:
   • Add the element to running.
   • Look up running - k in count. Add the result to answer.
   • Increment count[running] by 1.

The {0: 1} initialization handles the case where a subarray starts at index 0 and itself sums to k (i.e., running - k == 0).

Why the sliding window does not work here: Negative numbers mean that as you extend the window, the sum can decrease. There is no monotonic relationship between window size and sum, so the "shrink when too large" heuristic is invalid. The prefix sum approach handles negative numbers naturally.

Visual Dry Run#

Input: nums = [1, 2, 3], k = 3

At index 1 (running=3): running - k = 0, count[0] = 1 → subarray [1,2] sums to 3. At index 2 (running=6): running - k = 3, count[3] = 1 → subarray [3] sums to 3.

Result: 2. Correct!

Input: nums = [1, -1, 1], k = 1

Subarrays summing to 1: [1] at index 0, [1] at index 2, [1,-1,1] (full array). Answer = 3.

Solution (Optimal)#

from collections import defaultdict
 
def subarraySum(nums: list[int], k: int) -> int:
    # prefix_count[s] = number of times prefix sum s has been seen
    prefix_count = defaultdict(int)
    prefix_count[0] = 1  # Empty prefix (before any element)
 
    running = 0
    answer = 0
 
    for num in nums:
        running += num
        # Count subarrays ending here that sum to k
        answer += prefix_count[running - k]
        # Record this prefix sum
        prefix_count[running] += 1
 
    return answer

var subarraySum = function(nums, k) {
    // Map from prefix sum to count of occurrences
    const prefixCount = new Map([[0, 1]]);
 
    let running = 0;
    let answer = 0;
 
    for (const num of nums) {
        running += num;
        // Add count of previous prefix sums equal to (running - k)
        answer += (prefixCount.get(running - k) || 0);
        // Record this prefix sum
        prefixCount.set(running, (prefixCount.get(running) || 0) + 1);
    }
 
    return answer;
};

Complexity Analysis

The hash map approach is strictly optimal. The brute force and prefix-sum-array approaches both require O(n^2) time because they enumerate starting positions for each ending position.

Common Mistakes#

• Forgetting to initialize prefix_count[0] = 1. Without this, subarrays that start at index 0 and sum to k are missed. The {0: 1} initialization represents the empty prefix.
• Checking prefix_count[running - k] after updating the map. You must look up before inserting the current prefix sum. If you insert first, you might count a "subarray" from index i to itself (zero length), which is invalid.
• Assuming sliding window works. With negative numbers, the sliding window approach is incorrect. Do not conflate this problem with Maximum Subarray Sum (Kadane's algorithm) or Minimum Size Subarray Sum (two pointers on non-negative arrays).
• Not handling k = 0 correctly. When k = 0, you are counting subarrays that sum to zero. The {0: 1} initialization and the running sum approach handle this correctly — any time running - k == running has been seen before, that counts.
• Integer overflow in languages with fixed-size integers. With nums.length up to 2 * 10^4 and values up to 1000, the maximum prefix sum is 2 * 10^7, which fits in a 32-bit integer. In Java and C++, int is safe here; no need for long.

Follow-up Questions#

What if you need the longest subarray summing to k instead of the count? Track the first occurrence of each prefix sum (not the count). For each ending index j, check if running - k was seen before; if so, the subarray length is j - first_occurrence[running - k]. Take the maximum. This is LC 325.

What if k is replaced with "a multiple of k" (divisibility)? Use modular prefix sums. Track running % k. If the same remainder has been seen before, the subarray between those indices sums to a multiple of k. This is LC 523 Continuous Subarray Sum.

What if you want subarrays with exactly k ones (binary array)? A clever trick: count(exactly k) = count(at most k) - count(at most k-1). Each "at most" query can be answered with a sliding window since the window sum is monotonic in a binary array. This is LC 930.

Can this problem be solved with sliding window for positive-only arrays? Yes. With all positive numbers, the window sum increases monotonically as you extend right. You can shrink from the left when the sum exceeds k. For mixed-sign arrays, this breaks down.

How would you parallelize this for a very large array? Split the array into chunks. For each chunk, compute prefix sums locally and track the cumulative offset from the start of the array. Merge results by adjusting for the offset. This is the standard parallel prefix sum pattern.

Key Takeaways#

• LC 560 Subarray Sum Equals K is the canonical prefix-sum + hashmap interview problem.
• A subarray nums[i..j] sums to k iff prefix[j] - prefix[i-1] == k, i.e., prefix[i-1] == prefix[j] - k.
• Maintain a HashMap of prefix-sum frequencies; for each new prefix, add map.get(prefix - k, 0) to the answer.
• Initialize the map with {0: 1} to count subarrays starting at index 0.
• Sliding window does NOT work here because nums can contain negatives — the running sum is non-monotonic.
• Time and space are both O(n); a single pass is sufficient.
• Same prefix-sum trick generalizes to "subarrays divisible by k", "subarrays with at most k odd numbers", and exactly-k variants.

Related Problems#

• LC 560 — Subarray Sum Equals K: This problem.
• LC 523 — Continuous Subarray Sum: Subarrays summing to a multiple of k — uses prefix mod as the HashMap key.
• LC 974 — Subarray Sums Divisible by K: Count subarrays whose sum is divisible by k — same modular prefix sum trick.
• LC 325 — Maximum Size Subarray Sum Equals k (Premium): Longest subarray with sum k — store first occurrence of each prefix sum instead of count.
• LC 930 — Binary Subarrays With Sum: Count subarrays with exactly k ones — uses the complement count trick.
• LC 1248 — Count Number of Nice Subarrays: Count subarrays with exactly k odd numbers — isomorphic to LC 930.