Prefix Sum + Hash Map (Subarray Count)

The Intuition

Plain prefix sums answer range queries: the sum of nums[i..j] equals prefix[j+1] - prefix[i]. That is useful when the question fixes a range and asks for its sum. The reverse is more interesting: fix a target sum k and ask how many subarrays achieve it.

Algebra gives the rephrasing. A subarray ending at index j has sum k exactly when prefix[j+1] - prefix[i] = k for some i <= j+1. Rearrange: prefix[i] = prefix[j+1] - k. So the question reduces to: as the running prefix sum walks through the array, how many earlier prefix sums equal current - k?

That answer is constant time per index if a hash map records how often each prefix sum has appeared. One scan, O(n) time.

The seeding (prefix-sum 0 mapped to count 1) is essential. Without it, a subarray starting at index 0 with sum exactly k would not be counted, because the "earlier prefix sum" needed is 0 (the empty prefix), and the loop never explicitly inserts 0.

Three LeetCode problems sit in this family, all shown in the code below.

Subarray Sum Equals K (LC 560). Count the number of contiguous subarrays whose sum is exactly k. The map's key is the running prefix sum, the value is how many times that prefix sum has appeared so far. At each new prefix p, the answer for subarrays ending here is the count of times p - k has appeared.

Continuous Subarray Sum (LC 523). Return true if any contiguous subarray of length at least two has a sum that is a multiple of k. Two prefix sums whose difference is divisible by k share the same remainder modulo k. Track the first index where each remainder appeared. When the same remainder shows up again at index i, the subarray between them is divisible by k. The "length at least two" constraint becomes a check on the index gap.

Subarrays Divisible by K (LC 974). Count the number of contiguous subarrays with sum divisible by k. Same idea as 523 but the goal is a count instead of a yes/no, so the map stores the frequency of each remainder. One subtlety: in Go and Java, the % operator can return a negative result when the operand is negative, which would split the same congruence class across two map keys. Normalize the remainder into 0..k-1 before using it.

The same shape solves a family of problems by changing the key:

• Subarray sum equals k: key = prefix sum, value = count.
• Sum divisible by k: key = prefix sum mod k. Equal remainders mean the difference is divisible.
• Length-≥-2 with sum divisible by k: key = remainder, value = first index seen. Check the gap.
• Equal number of 0s and 1s: treat 0 as -1, then look for prefix sums seen earlier. Key = running sum.
• Number of subarrays with at most k odd numbers: turn into a counting problem with prefix counts of odds.

Negative remainders are a language gotcha. Python's % always returns a non-negative result for positive k. Go and Java's % can return a negative when the dividend is negative. Normalize with if rem < 0: rem += k whenever the input array can contain negatives.

When the order of insertion vs lookup is reversed, double counting happens. The current prefix_sum should not be in the map when its lookup runs, otherwise an empty subarray of length 0 would count as a valid match. Always look up first, then insert.

When to use

• Counting subarrays that satisfy a sum condition (equal to, divisible by, at most)
• The value at each index can be added or accumulated cleanly into a running statistic
• Need O(n) time, willing to use O(n) extra space
• The window has variable length (sliding window only works for monotone counts; this works in general)

When NOT to use

• The condition involves the actual elements of the subarray (e.g. "max element" or "all distinct"), not a sum
• Need the actual subarrays, not just the count (you can extend, but the structure changes)
• Memory is tight; if values are bounded and small, a fixed-size array can replace the map

Pattern Recognition

• "count subarrays whose sum equals K"
• "subarray with sum divisible by K"
• "longest subarray with sum K" (variant: store first index instead of count)
• "subarray with equal number of X and Y"

Variations

• Longest subarray with sum k: Same setup, but the value in the map is the first index where each prefix sum appeared. For each new prefix, the longest valid subarray ending here is i - first_index[prefix - k].
• Maximum sum subarray with constraint: Combine prefix sum with sliding window minimums (deque) for problems like "maximum sum subarray of size at most k".
• Range update, range sum: Use a Fenwick tree on the prefix sums for O(log n) updates.

Edge Cases

• Empty array (return 0)
• Array of all zeros, k = 0 (every prefix matches; result is n*(n+1)/2)
• Single element equals k (must be counted)
• Negative numbers in the array (sliding window does not work; this pattern still does)
• k larger than the total sum (result is 0)

Practice Problems

• [Medium] Subarray Sum Equals K
• [Medium] Continuous Subarray Sum
• [Medium] Subarray Sums Divisible by K
• [Medium] Contiguous Array
• [Hard] Maximum Sum of Subarray with at Least K Elements