🔑 How to Decide ==, >, or >= in Sliding
Window Problems
Step 1: Understand the Problem Requirement
Ask yourself:
• Do I need the sum exactly equal to k?
• Or do I need the sum at least (≥) k?
• Or do I need the sum at most (≤) k?
👉 This tells you what condition must trigger shrinking the window.
Step 2: Map Requirement → Window Condition
1. Exact sum (== k) problems
• Example: "Find number of subarrays whose sum = k"
• Shrink window only when sum > k (too big).
• Check result when sum == k.
while(sum > k) {
sum -= nums[left];
left++;
}
if(sum == k) result++;
2. Minimum length subarray with sum ≥ k
• Example: "Find the smallest subarray with sum ≥ k".
• Shrink as long as sum >= k because we want the smallest possible window.
• Update result before shrinking.
while(sum >= k) {
result = min(result, right - left + 1);
sum -= nums[left];
left++;
}
3. Maximum length subarray with sum ≤ k
• Example: "Find the longest subarray with sum ≤ k".
• Shrink only when sum > k (invalid).
• Update result after shrinking.
while(sum > k) {
sum -= nums[left];
left++;
}
result = max(result, right - left + 1);
Step 3: General Rule (Shortcut)
• If problem says “at least / ≥ k” → use while(sum >= k).
• If problem says “at most / ≤ k” → use while(sum > k).
• If problem says “exactly k” → shrink on > k, check answer on == k.
✅ With this, you can always figure out which while condition to use.
👉 Want me to show you how your original wrong code failed this rule and why the corrected one
matched perfectly?
Great question 🚀 You’re touching two very popular problems in
interviews:
1. Count subarrays with sum = 0
2. Count subarrays with sum = k (generalized form)
Both are solved with the prefix sum + hashmap technique. Let’s carefully break this down.
🔑 Step 1: What is a Prefix Sum?
• Prefix sum at index i = sum of elements from 0 to i.
• If you know prefix sums, you can find any subarray sum quickly:
sum(i..j)=prefix[j]−prefix[i−1]
🔑 Step 2: Core Idea for Subarray Sum = k
Suppose current prefix sum = currSum.
We want a subarray ending at current index with sum = k.
That means:
currSum−prevSum=k
So:
prevSum=currSum−k
If we’ve seen a prefix sum currSum - k before, then there exists a subarray with sum = k.
👉 This is why we use a map (unordered_map<int,int>) to store counts of prefix sums.
🟢 Example 1: Count subarrays with sum = 0
Code:
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> nums = {1, -1, 2, -2, 3};
unordered_map<int,int> mp;
int count = 0;
int prefix = 0;
mp[0] = 1; // important: to handle case when prefix itself is 0
for (int x : nums) {
prefix += x;
// if prefix has been seen before, that means subarray sum = 0
if([Link](prefix) != [Link]()) {
count += mp[prefix];
}
mp[prefix]++;
}
cout << "Count of subarrays with sum 0 = " << count << endl;
}
Why mp[0] = 1?
• To handle case where prefix sum itself is 0.
Example: [3, -3]. After first element, prefix=3. After second element, prefix=0. That
means the whole subarray [3, -3] has sum 0.
🟢 Example 2: Count subarrays with sum = k
We just extend the idea:
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> nums = {1,2,3, -2, 5};
int k = 5;
unordered_map<int,int> mp;
int count = 0;
int prefix = 0;
mp[0] = 1; // to handle subarray starting at index 0
for (int x : nums) {
prefix += x;
// check if there's a previous prefix sum = prefix - k
if([Link](prefix - k) != [Link]()) {
count += mp[prefix - k];
}
mp[prefix]++;
}
cout << "Count of subarrays with sum " << k << " = " << count << endl;
}
🔑 Why do we use a map?
• To remember how many times each prefix sum occurred.
• Because multiple previous indices may give valid subarrays.
• Example: nums = [1, -1, 1, -1], k = 0.
• prefix sums = [1, 0, 1, 0]
• We must count all possible subarrays, not just the first occurrence.
👉 Map stores frequency so we can add multiple contributions.
✅ Summary:
• Use prefix sum to reduce subarray sum problem into a simple difference check.
• Use map to store frequency of prefix sums (since many subarrays may exist).
• Formula: if(currSum - k exists in map) → count += mp[currSum -
k].
Do you want me to also show the difference between sliding window vs prefix sum + map
approaches, and when to use which?
Nice 🔥 — this is the “minimum length subarray” version of
the prefix-sum problems we just discussed.
Let’s carefully build the intuition step by step.
🔑 Step 1: Recap — Subarray sum with map
(counting version)
We know:
• If prefix[j] - prefix[i] == k, then subarray (i+1 … j) has sum k.
• In counting problems, we only care about how many such i’s exist. So we stored
frequencies in a map.
But for minimum length, frequency is not enough.
We also need the index where a prefix sum first occurred, so we can measure length = j - i.
👉 So now our map will be:
prefix_sum -> first_index_where_it_occurred
🟢 Step 2: Minimum Length Subarray with
Sum = 0
We want the shortest subarray with sum = 0.
Logic:
• Maintain prefix sum while iterating.
• If the same prefix sum appears again at index j and i, then prefix[j] - prefix[i]
= 0.
• Subarray (i+1 … j) has sum 0, length = j - i.
• To minimize length, we want earliest occurrence of a prefix sum, so we store only the first
index of each prefix sum in the map.
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> nums = {1, 2, -3, 4, -4, 2};
unordered_map<int,int> mp;
int prefix = 0;
int minLen = INT_MAX;
mp[0] = -1; // prefix sum = 0 at index -1 (helps handle from start)
for(int j = 0; j < [Link](); j++) {
prefix += nums[j];
if([Link](prefix) != [Link]()) {
int i = mp[prefix];
minLen = min(minLen, j - i);
} else {
// store only first occurrence
mp[prefix] = j;
}
}
if(minLen == INT_MAX) cout << "No subarray with sum 0";
else cout << "Minimum length = " << minLen;
}
Thinking process:
• If sum till index j is same as sum till index i,
⇒ elements between (i+1..j) sum to 0.
• We need shortest ⇒ store only the first time we saw a prefix sum (because later
occurrences would only give longer subarrays).
🟢 Step 3: Minimum Length Subarray with
Sum = k
Now generalize for k.
We want:
prefix[j]−prefix[i]=k⇒prefix[i]=prefix[j]−k
So at index j, we check if prefix[j] - k exists in the map.
If yes, subarray (i+1..j) has sum = k, length = j - i.
Again:
• To minimize length, we store the first index of each prefix sum.
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> nums = {2, 3, 1, 2, 4, 3};
int k = 7;
unordered_map<int,int> mp;
int prefix = 0, minLen = INT_MAX;
mp[0] = -1; // base case: subarray starting from index 0
for(int j = 0; j < [Link](); j++) {
prefix += nums[j];
if([Link](prefix - k) != [Link]()) {
int i = mp[prefix - k];
minLen = min(minLen, j - i);
}
if([Link](prefix) == [Link]()) {
mp[prefix] = j; // store first occurrence only
}
}
if(minLen == INT_MAX) cout << "No subarray with sum " << k;
else cout << "Minimum length = " << minLen;
}
🔑 Step 4: Why Map is Needed?
• Without map: we’d have to check all possible (i, j) pairs = O(n²).
• With map:
• Prefix sums convert subarray sum check into a constant-time lookup.
• Map stores where a prefix sum was first seen, so we can calculate length
immediately.
• This reduces time complexity to O(n).
🚦 When to use Sliding Window instead?
• If array has only positive numbers, we can use two pointers / sliding window because
once the sum exceeds k, moving left decreases sum.
• If array has negative numbers, sliding window fails (sum may increase when you shrink).
That’s when prefix sum + map is required.
✅ Summary:
• For counting subarrays → store frequency of prefix sums in map.
• For minimum length subarray → store first index of each prefix sum in map.
• Sliding window is faster but works only when all elements are non-negative.
Would you like me to also compare outputs of sliding window vs prefix-sum+map for the same
test case, so you clearly see when one fails and the other succeeds?