Subarray Sum Equals K
Mahabharata — Yudhishthira's Treasury — Counting the Exact Balance Transfers
पूर्वसंचयः यदि ज्ञातः तदा मध्यखण्डं सुलभम्। S - K यदि दृष्टम् पूर्वे — K-योगः तत्रास्ति ध्रुवम्॥
*If the prior accumulation is known, the middle section is easily found. Where S minus K was seen before — the sum K is certain there.*
The Story
After the Kurukshetra war, Yudhishthira was rebuilding the royal treasury. Each day's net transaction was recorded as a number in an array — positive for deposits, negative for withdrawals. He needed to know: how many contiguous stretches of days had a net transaction sum EXACTLY equal to K?
"For every possible start and end day," his treasurer suggested, "compute the sum. Count those equal to K." O(n²) — too slow for a ledger spanning thousands of days.
"The prefix sum approach," Vidura said, "transforms this into O(n)."
The key insight: define `prefixSum[i]` = sum of all transactions from day 0 to day i. Then the sum of days [j+1..i] = `prefixSum[i] - prefixSum[j]`.
We want: `prefixSum[i] - prefixSum[j] = K`, which means `prefixSum[j] = prefixSum[i] - K`.
"So as we build the running prefix sum," Vidura explained, "for each day i with prefix sum `S`, we ask: how many earlier days j had prefix sum `S - K`? Each such j represents a subarray [j+1..i] with sum exactly K."
"We store the COUNT of each prefix sum seen so far in a HashMap. Before processing day i, check `map.get(S - K)`. This count is the number of valid subarrays ending at i."
"Initialize the map with {0: 1} — the empty prefix (day 0, before any transactions) has sum 0, and it counts as one occurrence."
Vidura demonstrated with `nums = [1, 1, 1]`, K = 2:
map = {0:1} - i=0: S=1. Look for S-K=1-2=-1. map.get(-1)=0. count+=0. map={0:1, 1:1} - i=1: S=2. Look for S-K=2-2=0. map.get(0)=1. count+=1 (subarray [0..1]). map={0:1,1:1,2:1} - i=2: S=3. Look for S-K=3-2=1. map.get(1)=1. count+=1 (subarray [1..2]). map={0:1,1:1,2:1,3:1}
Answer: 2. The subarrays [0..1]=[1,1] and [1..2]=[1,1] both sum to 2.
"But what about `[1, 2, 1, 2, 1]` with K=3?" the treasurer asked. "There could be multiple subarrays ending at the same point."
`map = {0:1}` - i=0 (1): S=1. S-K=-2. count+=0. map={0:1,1:1} - i=1 (2): S=3. S-K=0. map[0]=1. count+=1. map={0:1,1:1,3:1} - i=2 (1): S=4. S-K=1. map[1]=1. count+=1. map={...,4:1} - i=3 (2): S=6. S-K=3. map[3]=1. count+=1. map={...,6:1} - i=4 (1): S=7. S-K=4. map[4]=1. count+=1.
Answer: 4.
"What if the same prefix sum appears multiple times?" Vidura continued. "Say `[1,-1,1,-1,1]` with K=1. At some prefix sum S, `map[S-K]` could be 3, meaning three earlier prefix sums equal S-K — three different subarrays all ending at i sum to K."
"The map stores COUNTS — not just a boolean — precisely for this reason. Multiple occurrences of the same prefix sum all become valid starting points."
Yudhishthira's treasury was analyzed in O(n) time. Every stretch of days with exact net transaction K was counted. The kingdom's finances were in order.
"This is the power of the prefix sum map," Vidura concluded. "Looking backward becomes looking up — O(1) per element instead of O(n) per element."
This is the Prefix Sum with HashMap technique for counting subarrays with sum equal to K.
The Treasurer's First Instinct
Try every pair of start and end indices. Compute sum. Count those equal to K. O(n²) time.
public int subarraySumBruteForce(int[] nums, int k) {
int count = 0;
for (int start = 0; start < nums.length; start++) {
int sum = 0;
for (int end = start; end < nums.length; end++) {
sum += nums[end];
if (sum == k) count++;
}
}
return count;
}Vidura's Prefix Sum Wisdom
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> prefixCount = new HashMap<>();
prefixCount.put(0, 1); // Empty prefix has sum 0, occurs once
int count = 0;
int sum = 0;
for (int n : nums) {
sum += n; // Build running prefix sum
// How many earlier prefix sums equal (sum - k)?
count += prefixCount.getOrDefault(sum - k, 0);
// Record this prefix sum
prefixCount.merge(sum, 1, Integer::sum);
}
return count;
}
// Test
public static void main(String[] args) {
System.out.println(new Solution().subarraySum(new int[]{1,1,1}, 2)); // 2
System.out.println(new Solution().subarraySum(new int[]{1,2,3}, 3)); // 2 ([1,2] and [3])
System.out.println(new Solution().subarraySum(new int[]{1,-1,1}, 1)); // 3
}Step-by-Step Walkthrough
nums = [1, -1, 1], k = 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Init: map={0:1}, sum=0, count=0
n=1: sum=1. Look for sum-k=0. map[0]=1. count=1.
(subarray [0..0]=[1] sums to 1) ✓
map={0:1, 1:1}
n=-1: sum=0. Look for sum-k=-1. map[-1]=0. count=1.
map={0:2, 1:1}
(now map[0]=2: empty prefix AND after [1,-1])
n=1: sum=1. Look for sum-k=0. map[0]=2! count=1+2=3.
(2 earlier prefix sums equal 0:
1st: empty prefix → subarray [0..2]=[1,-1,1]=1 ✓
2nd: after index 1 → subarray [2..2]=[1]=1 ✓)
map={0:2, 1:2}
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Return 3
The 3 subarrays with sum=1: [1], [1,-1,1], [1]Deep Insight
**Why initialize map with {0: 1}?** We need to count subarrays starting from index 0. If `sum == K` at index i, then the subarray [0..i] has sum K. For this to be counted, we need `map[sum - K] = map[0] = 1`. Without initialization, this case would be missed.
**Works with negative numbers and zeros:** Unlike the sliding window approach (which only works for positive numbers), the prefix sum map handles negative numbers and zeros correctly because it counts ALL prefix sums, not just the current window.
**The mathematical insight:** `sum[i] - sum[j] = K` ↔ `sum[j] = sum[i] - K` For each prefix sum we compute, we check how many previous prefix sums were exactly K less. Each match is a valid subarray.
**Space-time tradeoff:** O(n) space for the HashMap allows O(1) lookup per element, reducing O(n²) to O(n). This is the classic hash-based optimization.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | All O(n²) start-end pairs checked |
| Optimal | O(n) | O(n) | HashMap stores at most n distinct prefix sums |
Pattern Recognition
✅ Count subarrays with EXACT sum = K
✅ Array may contain negative numbers or zeros
✅ Prefix sum + HashMap for O(1) lookup
✅ Initialize map with {0:1} for subarrays starting at index 0
**LeetCode Trigger Phrases:**
→ "number of subarrays with sum equal to k"
→ "count contiguous subarrays" + "sum equals"
→ "negative numbers allowed" + count subarraysBhagavad Gita 2.50
बुद्धियुक्तो जहातीह उभे सुकृतदुष्कृते। तस्माद्योगाय युज्यस्व योगः कर्मसु कौशलम्॥
One endowed with wisdom abandons both good and evil deeds in this life. Therefore, devote yourself to yoga — yoga is skill in action.
Connection: The prefix sum map embodies 'skill in action' — instead of the exhausting recalculation of every subarray (brute force, attachment to repetition), it stores accumulated wisdom (the prefix sum map) and looks up answers in O(1). The running prefix sum carries forward all previous information efficiently, just as the yogi carries the essence of past actions (karma) without being burdened by recomputing them. The answer emerges not through force but through organized memory.