Subarray Sum Equals K (Prefix Sum with a Hash Map)

• This problem counts contiguous subarrays summing to exactly k, in an array with possible negatives.
• The prefix sum at index i is the sum of all elements from 0 to i.
• A subarray from j+1 to i sums to k when prefix[i] - prefix[j] = k, i.e., prefix[j] = prefix[i] - k.
• A hash map tracks how many times each prefix value has occurred.
• Seed the map with {0: 1} for the empty prefix; look up before insert.
• Time is O(N) and space is O(N).

What is the Subarray Sum Equals K problem?

Given an array of integers (possibly including negatives) and a target value k, count the total number of contiguous subarrays whose elements sum exactly to k. This is LeetCode 560.

For example, given [1, 1, 1] and k = 2, the answer is 2: subarrays [1, 1] starting at index 0 and [1, 1] starting at index 1.

How does the prefix-sum hash map work?

Define the prefix sum at index i as the sum of all elements from 0 through i. The sum of any subarray from j+1 to i equals prefix[i] - prefix[j]. This subarray sums to k when prefix[j] = prefix[i] - k.

So as we scan left to right maintaining a running prefix, the number of subarrays ending at the current index with sum k equals the number of times prefix - k has appeared as an earlier prefix sum.

package com.bank.service;

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

public class SubarraySumKService {

    /**
     * Counts continuous stretches of cash flows summing to exactly target.
     * Used by the National Bank of India reconciliation team.
     */
    public static int subarraySum(int[] flows, int k) {
        Map<Long, Integer> prefixCount = new HashMap<>();
        prefixCount.put(0L, 1); // Seed: empty prefix

        long prefix = 0;
        int count = 0;

        for (int flow : flows) {
            prefix += flow;
            // Look up before insert
            count += prefixCount.getOrDefault(prefix - k, 0);
            prefixCount.merge(prefix, 1, Integer::sum);
        }
        return count;
    }

    public static void main(String[] args) {
        int[] flows = {10000, -5000, 5000, -10000, 10000};
        int target = 10000;
        System.out.println("Stretches summing to Rs." + target
            + ": " + subarraySum(flows, target));
    }
}

javac -d out com/bank/service/SubarraySumKService.java
java -cp out com.bank.service.SubarraySumKService

Stretches summing to Rs.10000: 4

Why is the seed {0: 1} so important?

The seed represents the empty prefix before any element. Without it, a subarray starting at index 0 that sums to k would not be counted, because the lookup for prefix - k = 0 would find nothing. This is the classic off-by-one trap.

// WRONG: no seed
Map<Long, Integer> map = new HashMap<>(); // Missing seed
// A subarray [0..i] summing to k is missed because prefix-k=0 is not found

// CORRECT: seed with {0: 1}
Map<Long, Integer> map = new HashMap<>();
map.put(0L, 1); // Empty prefix counts as one occurrence

Why look up before inserting?

We look up prefix - k before recording the current prefix in the map. If we inserted first, we might match the current element against itself, counting a zero-length subarray.

Why does the sliding window fail here?

Sliding windows rely on the monotonicity of the running sum: adding elements increases the sum and removing elements decreases it. With negatives, adding an element might decrease the sum and removing one might increase it, breaking the invariant. The prefix-sum-with-hash-map method handles the general signed case.

What are the edge cases?

Several edge cases require attention.

• k = 0: counts subarrays summing to zero, which can exist even in positive arrays if they contain canceling elements.
• All zeros: every subarray sums to zero, giving N*(N+1)/2 subarrays when k = 0.
• Negative target: fully supported by the prefix difference.
• Single element equal to k: counted via the seed.

package com.bank.core;

public class SubarraySumEdgeCases {
    public static void main(String[] args) {
        // k = 0 with canceling elements
        System.out.println(subarraySum(new int[]{1, -1, 1, -1}, 0)); // 4

        // Single element equals k
        System.out.println(subarraySum(new int[]{5000}, 5000)); // 1

        // Negative target
        System.out.println(subarraySum(new int[]{-1, -2, 3}, -3)); // 1
    }

    static int subarraySum(int[] arr, int k) {
        java.util.Map<Long, Integer> map = new java.util.HashMap<>();
        map.put(0L, 1); long prefix = 0; int count = 0;
        for (int a : arr) { prefix += a; count += map.getOrDefault(prefix - k, 0); map.merge(prefix, 1, Integer::sum); }
        return count;
    }
}

4
1
1

What is the time and space complexity?

Time is O(N): one pass with O(1) amortized map operations per element. Space is O(N) for the hash map in the worst case (all distinct prefix sums).

How is this related to other prefix-sum problems?

This is the canonical prefix-sum counting pattern. Variations include:

| Problem | What to track in the map |
|---|---|
| Subarray sum = k | Prefix sum frequency |
| Subarray sum divisible by k | Prefix sum mod k frequency |
| Longest subarray sum = k | First occurrence of each prefix |
| Equal zeros and ones | First occurrence of transformed prefix |

What should a senior engineer know?

A senior engineer should understand these deeper aspects.

• Use long for prefix sums: integer overflow is possible on long financial sequences.
• The seed and ordering are the two correctness linchpins: getting either wrong produces subtle bugs.
• When to use this vs sliding window: the moment negatives appear, reach for prefix-sum-with-map. Sliding windows are for positive-only arrays.
• HashMap vs array: if the prefix range is bounded, an array-based frequency map is faster.