Sliding Window vs Prefix Sum + Hash
The Non-Negative Monotonicity Rule and the Negative Numbers Trap
Why negative numbers break sliding windows completely, and how prefix sum hash maps recover O(N) lookup for arbitrary integer arrays.
"Can the array numbers be negative, or does expanding the window move your condition in only one predictable direction?"
Ask this single question during the first two minutes of reading the problem prompt. The answer decides your fundamental pattern.
Think of a metro smart card transaction ledger. Every time you tap in or out, your balance is recorded. If your balance was Rs 120 at Rajiv Chowk and Rs 70 at Noida City Centre, the fare between those two stations is exactly Rs 120 minus Rs 70 = Rs 50. You do not need to walk between the stations or recount each rupee; the difference between two cumulative snapshots gives you the exact interval amount. Now think of a station turnstile counter that tracks the number of commuters entering in the last 15 minutes. It slides along the clock: new arrivals increment the count, and people who entered more than 15 minutes ago drop out. This works because people cannot un-enter the station (counts are strictly non-negative).
When to Choose Which Pattern
Sliding Window
Option A- ✓All array elements are strictly non-negative (>= 0).
- ✓The target condition is monotonic: expanding right strictly increases sum; advancing left strictly decreases sum.
- ✓You want O(1) auxiliary space without allocating hash map buckets.
- ✓The problem asks for minimum length, maximum length, or count under monotonic bounds.
Prefix Sum + Hash Map
Option B- ✓The array contains negative numbers, zeros, or arbitrary balance changes.
- ✓You need to find a subarray with an exact sum K, or count all subarrays summing to K.
- ✓The algebraic relation prefix[j] - prefix[i] = K translates into checking whether (current_prefix - K) exists in our hash map.
- ✓Array elements cannot be reordered or sorted.
Side-by-Side Worked Examples
Compare concrete implementations side by side to see how the code structure diverges.
Minimum Size Subarray Sum(LC 209)
LeetCode ↗The array contains strictly positive integers. Expand right and add nums[right] to current_sum. While current_sum >= target, record the window size (right - left + 1) and shrink the window from the left by subtracting nums[left]. Because numbers are positive, shrinking is guaranteed to decrease current_sum.
def minSubArrayLen(target: int, nums: list[int]) -> int:
left = 0
current_sum = 0
min_len = float('inf')
for right, val in enumerate(nums):
current_sum += val
while current_sum >= target:
min_len = min(min_len, right - left + 1)
current_sum -= nums[left]
left += 1
return min_len if min_len != float('inf') else 0Subarray Sum Equals K(LC 560)
LeetCode ↗Maintain running sum prefix. A subarray ending at current index sums to k if prefix - k was seen earlier. Add map[prefix - k] to total answer, then increment map[prefix]. Seed the map with {0: 1} before starting to account for valid subarrays starting at index 0.
def subarraySum(nums: list[int], k: int) -> int:
prefix_counts = {0: 1}
current_sum = 0
total_count = 0
for num in nums:
current_sum += num
diff = current_sum - k
if diff in prefix_counts:
total_count += prefix_counts[diff]
prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1
return total_countThe Decision Matrix
Negative Numbers
Breaks completely (monotonicity lost)
Handles negatives and zeros seamlessly
Extra Memory
O(1) auxiliary space
O(N) hash map storage
Subarray Query Type
Inequalities (>= K, <= K, at most K distinct elements)
Exact equality (sum == K, sum % K == 0)
State History
Only requires tracking current left and right boundaries
Requires frequency or index history of previous cumulative sums
| Evaluation Factor | Sliding Window | Prefix Sum + Hash Map |
|---|---|---|
| Negative Numbers | Breaks completely (monotonicity lost) | Handles negatives and zeros seamlessly |
| Extra Memory | O(1) auxiliary space | O(N) hash map storage |
| Subarray Query Type | Inequalities (>= K, <= K, at most K distinct elements) | Exact equality (sum == K, sum % K == 0) |
| State History | Only requires tracking current left and right boundaries | Requires frequency or index history of previous cumulative sums |
Where Candidates Go Wrong (Top Traps)
The LeetCode 560 sliding window trap
Forgetting the base seed {0: 1} in the prefix frequency map
Overwriting indices when searching for longest subarray
Related Walkthroughs in our DSA Course
Explore step-by-step solutions with 4-language code flaps (Java, C#, TS, Python) and visual memory dry runs.
Prefix Sum Pattern Primer
Subarray Sum Equals K (Negative Numbers Solution)
Maximum Subarray (Kadane Algorithm)
"Sliding window runs with O(1) auxiliary space but demands strict monotonicity (non-negative elements). Prefix sum with a hash map handles negative values and arbitrary integers, but trades away O(1) space for O(N) map storage and hash collision overhead."
Practice Real Indian Hiring Loops
See the exact problems asked at Flipkart, Swiggy, Razorpay, PhonePe, and Amazon with verified candidate reports and round structures.