Subarray Sum Equals K: Prefix Sum Plus a HashMap Counting currentSum Minus K

• Subarray Sum Equals K – counts contiguous subarrays whose elements sum to exactly K, including negative numbers.
• Prefix-sum identity – a subarray sums to K when prefix[j] - prefix[i] = K, meaning prefix[i] = currentSum - K.
• HashMap – maps each prefix-sum value to its occurrence count; lookup of currentSum - K gives the number of valid starting points.
• Seed – map.put(0, 1) handles subarrays starting from index 0.
• O(n) time, O(n) space – one pass through the array with a map of at most n entries.

What is the Subarray Sum Equals K problem?

Given an integer array (which may contain negative numbers) and an integer K, count the total number of contiguous subarrays whose elements sum to exactly K. For example, in [1, 1, 1] with K = 2, the answer is 2 (subarrays [1,1] starting at index 0 and index 1).

Why can't a sliding window solve this?

A sliding window assumes that extending the window only increases the sum and shrinking only decreases it. With negative numbers, adding an element might decrease the sum, breaking the monotonic assumption. The prefix-sum-plus-map method works regardless of sign.

How does the prefix-sum-plus-HashMap technique work?

The core identity: a subarray from index i+1 to j sums to K exactly when prefix[j] - prefix[i] = K. Rearranging: prefix[i] = prefix[j] - K = currentSum - K. So at each position j, the number of valid subarrays ending at j equals the number of earlier prefix values equal to currentSum - K.

Array: [1, 2, -1, 3]   K = 3

index  value  currentSum  currentSum-K  map(before)        count
  -      -       0            -         {0:1}               0
  0      1       1           -2         {0:1}→{0:1,1:1}     0
  1      2       3            0         {0:1}→count+=1       1
                                        {0:1,1:1,3:1}       
  2     -1       2           -1         {}→count+=0          1
                                        {0:1,1:1,3:1,2:1}
  3      3       5            2         {2:1}→count+=1       2

Answer: 2 (subarrays [1,2] and [2,-1,3])

How do you implement it? (with code)

package com.bank.compliance;

import java.util.HashMap;
import java.util.Map;

public class SubarraySumEqualsK {

    public static int countSubarrays(int[] movements, int k) {
        Map<Integer, Integer> prefixCounts = new HashMap<>();
        prefixCounts.put(0, 1);  // seed: prefix sum 0 seen once

        int sum = 0;
        int count = 0;

        for (int movement : movements) {
            sum += movement;
            // How many earlier prefixes equal sum - k?
            count += prefixCounts.getOrDefault(sum - k, 0);
            // Record current prefix sum
            prefixCounts.merge(sum, 1, Integer::sum);
        }
        return count;
    }

    public static void main(String[] args) {
        int[] dailyMovements = {100, 200, -100, 300, -200, 400};
        int target = 300;
        System.out.println("Subarrays summing to " + target + ": "
            + countSubarrays(dailyMovements, target));
    }
}

Subarrays summing to 300: 4

Why seed the map with (0, 1)?

The seed handles subarrays that start at index 0. If currentSum equals K at some index, then currentSum - K = 0, and the seeded zero contributes one count. Without the seed, these subarrays would be missed. Forgetting this seed is the single most common bug.

// Without seed: misses subarrays starting at index 0
Map<Integer, Integer> map = new HashMap<>();
// map is empty, so sum-K=0 lookup returns 0 even when sum==K

// With seed: correctly counts them
map.put(0, 1);

Why add to count before recording?

You add to the count before recording the current prefix sum so you never count a zero-length subarray (from j to j, exclusive of start). The current sum has not been added to the map yet when you check.

Why store counts instead of just presence?

A given prefix sum can recur multiple times. Each recurrence is a distinct valid starting point for a subarray ending at the current index. Storing only presence (boolean) would undercount.

What are the edge cases?

• All elements are K – each single element is a valid subarray.
• K = 0 – count subarrays that sum to zero, including those where elements cancel out.
• Negative numbers – handled correctly by the prefix-sum technique.
• Single element equals K – counted correctly via the seed.
• Empty array – return 0.

How is this different from Two Sum?

Two Sum finds pairs with a given sum in an unordered set. Subarray Sum Equals K finds contiguous ranges with a given sum in a sequential array. Both use a HashMap lookup, but the key in Two Sum is the complement of a single value, while here it is the complement of a running prefix sum.

What are common interview follow-up questions?

• What about returning the actual subarrays? – Store lists of indices in the map instead of counts.
• What about the longest subarray summing to K? – Store first occurrence index instead of count (see Contiguous Array).
• What if all values are positive? – A sliding window works and uses O(1) space.
• Time and space? – O(n) time, O(n) space.