Pattern Guide
HashMap + Prefix Sum Patterns
"Count subarrays with target sum, equal 0s and 1s, balanced strings."
Combining prefix sums with HashMaps enables O(n) solutions for subarray counting problems that would be O(n²) with naive approaches. Pattern: for each index i, look up whether (prefix[i] - target) has been seen before. Applications: count subarrays with sum k, find longest subarray with equal 0s and 1s, count balanced substrings, subarray XOR equals target.
Problems you can solve with this pattern
4 problems · click any to start solving
// Count subarrays with sum = k
function subarraySum(nums, k) {
const map = new Map([[0, 1]]);
let sum = 0, count = 0;
for (const n of nums) {
sum += n;
count += (map.get(sum - k) || 0);
map.set(sum, (map.get(sum) || 0) + 1);
}
return count;
}
// Longest subarray with equal 0s and 1s (transform 0→-1, find longest sum=0 subarray)
function longestEqualBinary(nums) {
const map = new Map([[0, -1]]); // prefix sum → first occurrence index
let sum = 0, maxLen = 0;
for (let i = 0; i < nums.length; i++) {
sum += nums[i] === 0 ? -1 : 1;
if (map.has(sum)) maxLen = Math.max(maxLen, i - map.get(sum));
else map.set(sum, i);
}
return maxLen;
}HashMap prefix pattern: maintain prefix sum and a map of {prefix_sum → earliest_index} or {prefix_sum → count}. For "longest subarray with sum = k": store earliest index for each prefix. For "count subarrays with sum = k": store count of each prefix. XOR variant: XOR has inverse of itself, so XOR prefix works identically. Transform 0→-1 to turn "equal count" problems into "sum = 0" problems.
// Count subarrays with sum = k
function subarraySum(nums, k) {
const map = new Map([[0, 1]]);
let sum = 0, count = 0;
for (const n of nums) {
sum += n;
count += (map.get(sum - k) || 0);
map.set(sum, (map.get(sum) || 0) + 1);
}
return count;
}
// Longest subarray with equal 0s and 1s (transform 0→-1, find longest sum=0 subarray)
function longestEqualBinary(nums) {
const map = new Map([[0, -1]]); // prefix sum → first occurrence index
let sum = 0, maxLen = 0;
for (let i = 0; i < nums.length; i++) {
sum += nums[i] === 0 ? -1 : 1;
if (map.has(sum)) maxLen = Math.max(maxLen, i - map.get(sum));
else map.set(sum, i);
}
return maxLen;
}- Count subarrays with sum = k: map stores {prefix → count}, look up (prefix - k)
- Longest subarray with sum = k: map stores {prefix → first_index}, look up (prefix - k)
- Divisibility: store remainders; two same remainders → divisible subarray between them
Transform tricks:
- Equal 0s and 1s: map 0→-1, find sum=0 subarray
- At most k distinct: convert to "exactly k" via atMost(k) - atMost(k-1)
- Divisible by k: use modular arithmetic on prefix sums
Handle negatives in mod: Always use ((x % k) + k) % k to get non-negative remainder.