The combination of prefix sum and hash maps is one of the most powerful techniques in algorithmic problem solving. It transforms O(n²) subarray sum problems into O(n) optimal solutions.
You've seen prefix sum for range queries. But what about finding all subarrays with a target sum? Or counting how many subarrays meet a condition? That's where the hash map comes in.
This pattern appears in dozens of medium and hard LeetCode problems. It's a favorite in FAANG interviews. And once you understand the template, you can solve an entire class of subarray problems in minutes.
This guide will teach you why hash maps are needed, the complete template, common patterns, and how to avoid the mistakes that cause wrong answers.
Use prefix sum + hash map when:
Template:
count = 0
prefix_sum = 0
sum_count = {0: 1} # Critical: initialize with {0: 1}
for num in nums:
prefix_sum += num
if prefix_sum - k in sum_count:
count += sum_count[prefix_sum - k]
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
return countTime: O(n), Space: O(n)
Basic prefix sum is great for range queries when you know the indices:
# If you know i and j, you can get sum(i, j) in O(1)
sum_range = prefix[j+1] - prefix[i]But what if you don't know the indices? What if you need to find all subarrays with sum equal to k?
Naive approach (O(n²)):
count = 0
for i in range(len(nums)):
for j in range(i, len(nums)):
if sum(nums[i:j+1]) == k:
count += 1
# Time: O(n²) - check all pairsWe need a way to find matching subarrays in one pass.
Key observation: If prefix[j] - prefix[i] = k, then the subarray from i+1 to j has sum k.
We can rearrange this:
prefix[j] - prefix[i] = k
prefix[i] = prefix[j] - kThe insight: As we iterate and compute prefix[j], we can check if prefix[j] - k exists in our hash map. If it does, we've found a subarray with sum k.
Visual example:
nums = [1, 2, 3, 4], k = 6
i=0: num=1, prefix=1
Check if (1 - 6) = -5 exists? No
Add {1: 1}
i=1: num=2, prefix=3
Check if (3 - 6) = -3 exists? No
Add {3: 1}
i=2: num=3, prefix=6
Check if (6 - 6) = 0 exists? Yes! (from initialization)
Found subarray [1,2,3] with sum 6
count = 1
Add {6: 1}
i=3: num=4, prefix=10
Check if (10 - 6) = 4 exists? No
Add {10: 1}
Result: 1 subarray foundWhat if multiple prefix sums have the same value?
nums = [1, -1, 1, -1, 1], k = 0
prefix sums: 0, 1, 0, 1, 0, 1
When prefix = 0 appears multiple times, each occurrence can pair
with other occurrences to form subarrays with sum 0.
We need to count ALL valid pairs, so we store frequency.def subarray_sum_equals_k(nums: List[int], k: int) -> int:
"""
Count subarrays with sum equal to k.
Time: O(n)
Space: O(n)
"""
count = 0
prefix_sum = 0
# Key: prefix sum, Value: frequency
# Initialize with {0: 1} to handle subarrays starting from index 0
sum_count = {0: 1}
for num in nums:
# Update running prefix sum
prefix_sum += num
# Check if (prefix_sum - k) exists
# If yes, we found subarray(s) with sum k
if prefix_sum - k in sum_count:
count += sum_count[prefix_sum - k]
# Add current prefix sum to map
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
return count
# Test
print(subarray_sum_equals_k([1, 2, 3, 4], 6)) # 1 ([1,2,3])
print(subarray_sum_equals_k([1, 1, 1], 2)) # 2 ([1,1] twice)
print(subarray_sum_equals_k([1, -1, 0], 0)) # 3 ([1,-1], [0], [1,-1,0])function subarraySumEqualsK(nums, k) {
let count = 0;
let prefixSum = 0;
const sumCount = new Map([[0, 1]]);
for (const num of nums) {
prefixSum += num;
if (sumCount.has(prefixSum - k)) {
count += sumCount.get(prefixSum - k);
}
sumCount.set(prefixSum, (sumCount.get(prefixSum) || 0) + 1);
}
return count;
}
// Test
console.log(subarraySumEqualsK([1, 2, 3, 4], 6)); // 1
console.log(subarraySumEqualsK([1, 1, 1], 2)); // 2
console.log(subarraySumEqualsK([1, -1, 0], 0)); // 3public int subarraySumEqualsK(int[] nums, int k) {
int count = 0;
int prefixSum = 0;
Map<Integer, Integer> sumCount = new HashMap<>();
sumCount.put(0, 1);
for (int num : nums) {
prefixSum += num;
if (sumCount.containsKey(prefixSum - k)) {
count += sumCount.get(prefixSum - k);
}
sumCount.put(prefixSum, sumCount.getOrDefault(prefixSum, 0) + 1);
}
return count;
}Given an array of integers and an integer k, return the total number of subarrays whose sum equals k.
Example:
Input: nums = [1, 2, 3], k = 3
Output: 2
Explanation: [1,2] and [3] both have sum 3def subarraySum(nums: List[int], k: int) -> int:
count = 0
prefix_sum = 0
sum_count = {0: 1}
for num in nums:
prefix_sum += num
# If (prefix_sum - k) exists, we found subarray(s)
if prefix_sum - k in sum_count:
count += sum_count[prefix_sum - k]
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
return countTrace for nums = [1, 2, 3], k = 3:
Initial: sum_count = {0: 1}, prefix_sum = 0, count = 0
i=0: num=1
prefix_sum = 1
Check: (1 - 3) = -2 in map? No
sum_count = {0: 1, 1: 1}
i=1: num=2
prefix_sum = 3
Check: (3 - 3) = 0 in map? Yes! count += 1
Found subarray [1,2] with sum 3
sum_count = {0: 1, 1: 1, 3: 1}
count = 1
i=2: num=3
prefix_sum = 6
Check: (6 - 3) = 3 in map? Yes! count += 1
Found subarray [3] with sum 3
sum_count = {0: 1, 1: 1, 3: 1, 6: 1}
count = 2
Result: 2Time: O(n)
Space: O(n)
Comparison with brute force:
Given an array and an integer k, check if there exists a good subarray (length ≥ 2) whose sum is a multiple of k.
Example:
Input: nums = [23, 2, 4, 6, 7], k = 6
Output: true
Explanation: [2, 4] has sum 6, which is divisible by 6def checkSubarraySum(nums: List[int], k: int) -> bool:
"""
Use modulo arithmetic with prefix sum.
Key insight: If two prefix sums have the same remainder
when divided by k, the subarray between them is divisible by k.
"""
# Key: remainder, Value: earliest index
remainder_index = {0: -1} # Handle subarray from start
prefix_sum = 0
for i, num in enumerate(nums):
prefix_sum += num
remainder = prefix_sum % k
if remainder in remainder_index:
# Check if subarray length >= 2
if i - remainder_index[remainder] >= 2:
return True
else:
# Store earliest index for this remainder
remainder_index[remainder] = i
return False
# Test
print(checkSubarraySum([23, 2, 4, 6, 7], 6)) # True
print(checkSubarraySum([23, 2, 6, 4, 7], 6)) # True
print(checkSubarraySum([23, 2, 6, 4, 7], 13)) # FalseMathematical insight:
If prefix[j] % k = prefix[i] % k, then:
(prefix[j] - prefix[i]) % k = 0This means the subarray from i+1 to j is divisible by k.
Trace for nums = [23, 2, 4, 6, 7], k = 6:
remainder_index = {0: -1}
i=0: num=23, prefix=23, remainder=23%6=5
5 not in map, add {5: 0}
remainder_index = {0: -1, 5: 0}
i=1: num=2, prefix=25, remainder=25%6=1
1 not in map, add {1: 1}
remainder_index = {0: -1, 5: 0, 1: 1}
i=2: num=4, prefix=29, remainder=29%6=5
5 in map at index 0!
Length = 2 - 0 = 2 >= 2 ✓
Return True
Subarray [2, 4] from index 1 to 2 has sum 6, divisible by 6We need to check if the subarray length is ≥ 2. Storing the earliest index for each remainder allows us to maximize the subarray length.
Count the number of non-empty subarrays with sum divisible by k.
Example:
Input: nums = [4, 5, 0, -2, -3, 1], k = 5
Output: 7
Explanation: Subarrays [4,5,0,-2,-3,1], [5], [5,0], [5,0,-2,-3], [0], [0,-2,-3], [-2,-3]def subarraysDivByK(nums: List[int], k: int) -> int:
"""
Count subarrays divisible by k using modulo arithmetic.
Key: Handle negative remainders correctly.
"""
count = 0
prefix_sum = 0
# Key: remainder, Value: frequency
remainder_count = {0: 1}
for num in nums:
prefix_sum += num
# Handle negative remainders: (-1) % 5 = 4 in math, but -1 in Python
remainder = ((prefix_sum % k) + k) % k
if remainder in remainder_count:
count += remainder_count[remainder]
remainder_count[remainder] = remainder_count.get(remainder, 0) + 1
return count
# Test
print(subarraysDivByK([4, 5, 0, -2, -3, 1], 5)) # 7
print(subarraysDivByK([5], 9)) # 0The problem: In Python, -1 % 5 = -1, but mathematically we want 4.
The fix: ((prefix_sum % k) + k) % k
Example:
prefix_sum = -1, k = 5
Wrong: -1 % 5 = -1
Correct: ((-1 % 5) + 5) % 5 = (-1 + 5) % 5 = 4 % 5 = 4This ensures all remainders are in the range [0, k-1].
Find the maximum length of a contiguous subarray with equal number of 0s and 1s.
Example:
Input: nums = [0, 1, 0]
Output: 2
Explanation: [0, 1] or [1, 0] both have equal 0s and 1sdef findMaxLength(nums: List[int]) -> int:
"""
Transform problem: treat 0 as -1, find subarray with sum 0.
"""
max_len = 0
prefix_sum = 0
# Key: prefix sum, Value: earliest index
sum_index = {0: -1} # Handle subarray from start
for i, num in enumerate(nums):
# Treat 0 as -1, 1 as +1
prefix_sum += 1 if num == 1 else -1
if prefix_sum in sum_index:
# Found subarray with sum 0 (equal 0s and 1s)
max_len = max(max_len, i - sum_index[prefix_sum])
else:
# Store earliest index for this sum
sum_index[prefix_sum] = i
return max_len
# Test
print(findMaxLength([0, 1])) # 2
print(findMaxLength([0, 1, 0])) # 2
print(findMaxLength([0, 0, 1, 0, 0, 0, 1, 1])) # 6Transformation: Treat 0 as -1 and 1 as +1.
Now, a subarray with equal 0s and 1s has sum 0.
Example:
Original: [0, 1, 0, 1]
Transform: [-1, 1, -1, 1]
Prefix: [0, -1, 0, -1, 0]
When prefix sum repeats (e.g., 0 at index 0 and 2),
the subarray between them has sum 0.❌ Wrong:
sum_count = {} # Missing base caseWhy it's wrong: Misses subarrays starting from index 0.
✅ Correct:
sum_count = {0: 1} # Handle subarrays from startSee guide: Hash Map Initialization
❌ Wrong:
for num in nums:
prefix_sum += num
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
if prefix_sum - k in sum_count: # Check AFTER update
count += sum_count[prefix_sum - k]Why it's wrong: Might count the current element as a subarray by itself incorrectly.
✅ Correct:
for num in nums:
prefix_sum += num
if prefix_sum - k in sum_count: # Check BEFORE update
count += sum_count[prefix_sum - k]
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1Different problem types need different approaches:
Counting subarrays: Store frequency
sum_count = {0: 1}
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1Finding longest subarray: Store earliest index
sum_index = {0: -1}
if prefix_sum not in sum_index:
sum_index[prefix_sum] = i❌ Wrong:
remainder = prefix_sum % k # Wrong for negative numbers✅ Correct:
remainder = ((prefix_sum % k) + k) % k # Handles negativesTime Complexity: O(n)
Space Complexity: O(n)
Comparison:
| Approach | Time | Space | Notes |
|---|---|---|---|
| Brute force | O(n²) | O(1) | Check all subarrays |
| Prefix sum + hash map | O(n) | O(n) | Optimal for this problem type |
| Sliding window | O(n) | O(1) | Only works for positive numbers |
Master this pattern with these problems:
Beginner:
Intermediate:
3. Continuous Subarray Sum (#523) - Modulo arithmetic
4. Subarray Sums Divisible by K (#974) - Handle negative remainders
5. Contiguous Array (#525) - Transform to sum = 0
Advanced:
6. Maximum Size Subarray Sum Equals k (#325) - Find longest, not count
7. Count Number of Nice Subarrays (#1248) - Transform to prefix sum
8. Binary Subarrays With Sum (#930) - Binary array variant
Q: Why do we need {0: 1} initialization?
A: To handle subarrays starting from index 0. Without it, we'd miss cases like [1, 2, 3] with target 6. See Hash Map Initialization.
Q: When should I use hash map vs sliding window?
A: Use hash map when:
Use sliding window when:
See Prefix Sum vs Sliding Window.
Q: How do I handle negative remainders?
A: Use ((prefix_sum % k) + k) % k to ensure remainders are in [0, k-1].
Q: Should I store frequency or index?
A: Depends on the problem:
Q: Can I use this for maximum subarray sum?
A: No, use Kadane's algorithm for that. This pattern is for exact target sum, not maximum.
The prefix sum + hash map combination is a powerful technique that solves subarray sum problems in linear time.
Key principles:
{0: 1} for subarrays from startThe template:
count = 0
prefix_sum = 0
sum_count = {0: 1}
for num in nums:
prefix_sum += num
if prefix_sum - k in sum_count:
count += sum_count[prefix_sum - k]
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
return countWhen to use:
Master this template, and you'll solve subarray sum problems with confidence. For more patterns, see the complete prefix sum guide, 1D template, and hash map initialization.
Next time you see "subarray with sum equals k," reach for prefix sum + hash map.
LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free