You see a problem: "Find subarrays with sum equals k." You think: "Sliding window!"
But then you notice: the array has negative numbers. Your sliding window solution fails.
This is where prefix sum + hash map comes in—the pattern that handles what sliding window cannot.
This combination is one of the most powerful hash map techniques. It appears in 20+ LeetCode problems, from "Subarray Sum Equals K" to "Continuous Subarray Sum" to "Subarray Sum Divisible by K." But the pattern isn't intuitive—it requires understanding both prefix sums and complement search.
This guide will teach you:
Master this, and subarray sum problems with negative numbers become solvable.
Problem: Count subarrays with sum equals k.
Brute force:
count = 0
for i in range(len(nums)):
current_sum = 0
for j in range(i, len(nums)):
current_sum += nums[j]
if current_sum == k:
count += 1
# O(n²) timeYou might think: "Use sliding window!"
# WRONG - doesn't work with negative numbers
left = 0
current_sum = 0
count = 0
for right in range(len(nums)):
current_sum += nums[right]
while current_sum > k: # When to shrink?
current_sum -= nums[left]
left += 1
if current_sum == k:
count += 1Why it fails: With negative numbers, shrinking doesn't guarantee the sum decreases. You lose the monotonicity property that sliding window requires.
Example:
nums = [1, -1, 1, 1], k = 2
At right=2: sum=1, should we shrink?
If we shrink, we might miss valid subarrays!For detailed comparison, see Sliding Window vs Prefix Sum.
Prefix sum lets us compute any subarray sum in O(1):
# Build prefix sum
prefix = [0]
for num in nums:
prefix.append(prefix[-1] + num)
# Sum from i to j
subarray_sum = prefix[j+1] - prefix[i]But we still need to check all pairs (i, j) → O(n²).
This is where hash map comes in.
If prefix[j] - prefix[i] = k, then subarray from i+1 to j has sum k.
Rearrange: prefix[i] = prefix[j] - k
So for each position j:
prefix[j]prefix[j] - k exists in our hash mapkKey insight: Store prefix sums in a hash map for O(1) lookup!
nums = [1, 2, 3, 4], k = 6
Prefix sums: [0, 1, 3, 6, 10]
At j=3 (prefix=6):
Looking for prefix[i] = 6 - 6 = 0
Found at i=0!
Subarray [1,2,3] has sum 6 ✓
At j=4 (prefix=10):
Looking for prefix[i] = 10 - 6 = 4
Not found (no subarray ending at index 3 with sum 6)What if the same prefix sum appears multiple times?
nums = [1, -1, 1, -1], k = 0
Prefix sums: [0, 1, 0, 1, 0]
↑ ↑ ↑
Three times prefix=0!Each occurrence of prefix[j] - k represents a valid subarray.
Solution: Store frequency of each prefix sum.
def subarraySum(nums: List[int], k: int) -> int:
"""
Count subarrays with sum equals k.
Time: O(n)
Space: O(n)
"""
count = 0
prefix_sum = 0
sum_count = {0: 1} # CRITICAL: Initialize with {0: 1}
for num in nums:
prefix_sum += num
# Check if (prefix_sum - k) exists
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 countCritical points:
{0: 1}: Handles subarrays starting from index 0public int subarraySum(int[] nums, int k) {
int count = 0;
int prefixSum = 0;
Map<Integer, Integer> sumCount = new HashMap<>();
sumCount.put(0, 1); // Critical initialization
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;
}function subarraySum(nums, k) {
let count = 0;
let prefixSum = 0;
const sumCount = new Map([[0, 1]]); // Critical initialization
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;
}This is the #1 mistake people make with this pattern.
Without initialization:
nums = [1, 2, 3], k = 3
sum_count = {} # Wrong!
i=0: prefix=1, check 1-3=-2 (not found), add {1: 1}
i=1: prefix=3, check 3-3=0 (not found!), add {1: 1, 3: 1}
i=2: prefix=6, check 6-3=3 (found!), count=1
Result: 1 (WRONG - should be 2, missing [1,2] and [3])With initialization:
nums = [1, 2, 3], k = 3
sum_count = {0: 1} # Correct!
i=0: prefix=1, check 1-3=-2 (not found), add {0: 1, 1: 1}
i=1: prefix=3, check 3-3=0 (found!), count=1, add {0: 1, 1: 1, 3: 1}
i=2: prefix=6, check 6-3=3 (found!), count=2, add {0: 1, 1: 1, 3: 1, 6: 1}
Result: 2 ✓ (found [1,2] and [3])Conceptual meaning: "There's one way to get sum 0: take nothing (empty prefix)."
Practical effect: Handles subarrays that start from index 0.
When prefix[j] = k, we need prefix[i] = 0 (i.e., subarray from 0 to j).
For more debugging tips, see Subarray Sum Mistakes.
Problem: Count subarrays with sum equals k.
Full solution with trace:
def 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 in sum_count:
count += sum_count[prefix_sum - k]
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
return countTrace example:
nums = [1, 2, 3], k = 3
Step num prefix check sum_count count
----- --- ------ -------------- ------------------------- -----
init - 0 - {0: 1} 0
0 1 1 1-3=-2 (no) {0: 1, 1: 1} 0
1 2 3 3-3=0 (yes!) {0: 1, 1: 1, 3: 1} 1
2 3 6 6-3=3 (yes!) {0: 1, 1: 1, 3: 1, 6: 1} 2
Found 2 subarrays: [1,2] and [3]Complexity: O(n) time, O(n) space
Problem: Check if array has subarray (size ≥ 2) with sum divisible by k.
Key insight: If two prefix sums have the same remainder when divided by k, the subarray between them is divisible by k.
def checkSubarraySum(nums: List[int], k: int) -> bool:
"""
Use modulo of prefix sums.
Time: O(n)
Space: O(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 FalseWhy it works:
If prefix[j] % k == prefix[i] % k, then:
(prefix[j] - prefix[i]) % k == 0
→ subarray from i+1 to j is divisible by kExample:
nums = [23, 2, 4, 6, 7], k = 6
Prefix: [0, 23, 25, 29, 35, 42]
Modulo: [0, 5, 1, 5, 5, 0]
↑ ↑ ↑
Same remainder 5!
At i=3: remainder=5, found at i=1, distance=2 ✓
Subarray [2,4,6] has sum 12, divisible by 6Problem: Count subarrays with sum divisible by k.
def subarraysDivByK(nums: List[int], k: int) -> int:
"""
Count subarrays with sum divisible by k.
Time: O(n)
Space: O(k)
"""
count = 0
prefix_sum = 0
remainder_count = {0: 1} # Critical initialization
for num in nums:
prefix_sum += num
remainder = prefix_sum % k
# Handle negative remainders
if remainder < 0:
remainder += k
if remainder in remainder_count:
count += remainder_count[remainder]
remainder_count[remainder] = remainder_count.get(remainder, 0) + 1
return countKey difference from #523: Count all subarrays (not just check existence).
Handling negative remainders:
# Python's % can return negative
-5 % 3 = 1 (in Python) # But we want positive remainder
# Fix: add k if negative
remainder = prefix_sum % k
if remainder < 0:
remainder += kThe same pattern works with XOR instead of sum.
def xorQueries(arr: List[int], queries: List[List[int]]) -> List[int]:
"""
Prefix XOR for range queries.
Time: O(n + q)
Space: O(n)
"""
# Build prefix XOR
prefix_xor = [0]
for num in arr:
prefix_xor.append(prefix_xor[-1] ^ num)
# Answer queries
result = []
for left, right in queries:
# XOR property: a ^ a = 0
result.append(prefix_xor[right + 1] ^ prefix_xor[left])
return resultWhy it works: XOR has the property a ^ a = 0, similar to subtraction.
Does the array have negative numbers?
├─ Yes → Use prefix sum + hash map
└─ No → Can you use sliding window?
├─ Finding subarrays with exact sum → Prefix sum + hash map
├─ Finding longest/shortest with condition → Sliding window
└─ Counting subarrays → Prefix sum + hash map| Problem Type | Negative Numbers? | Pattern |
|---|---|---|
| Subarray sum = k | Yes | Prefix sum + hash map |
| Subarray sum = k | No | Prefix sum + hash map (still works) |
| Longest subarray sum ≤ k | No | Sliding window |
| Longest subarray sum ≤ k | Yes | Can't use sliding window easily |
| Count subarrays sum = k | Any | Prefix sum + hash map |
Rule of thumb: If you need exact sum or have negative numbers, use prefix sum + hash map.
❌ Wrong:
sum_count = {} # Missing {0: 1}✅ Correct:
sum_count = {0: 1}❌ Wrong (update before checking):
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
if prefix_sum - k in sum_count:
count += sum_count[prefix_sum - k]✅ Correct (check before updating):
if prefix_sum - k in sum_count:
count += sum_count[prefix_sum - k]
sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1❌ Wrong (in languages where % can be negative):
remainder = prefix_sum % k
# In Python, -5 % 3 = 1, but in Java/C++, -5 % 3 = -2✅ Correct:
remainder = prefix_sum % k
if remainder < 0:
remainder += k❌ Wrong:
# Trying to use sliding window with negative numbers
# Doesn't work - monotonicity is broken✅ Correct:
# Use prefix sum + hash map insteadBuilding and querying: O(n)
Hash map size: O(n) worst case
Optimization: For modulo problems, space is bounded by k.
Prefix sum + hash map is the pattern for subarray sum problems with negative numbers.
Key principles:
prefix[i] = prefix[j] - kThe template:
count = 0
prefix_sum = 0
sum_count = {0: 1} # Critical!
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:
When NOT to use:
Common mistakes:
Next steps:
Master this pattern, and subarray sum problems with negative numbers become solvable.
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