Fixed vs Variable Window
C++
// FIXED WINDOW — size k stays constant
int fixedWindow(vector<int>& nums, int k) {
int windowSum=0, maxSum=0;
for(int i=0;i<k;i++) windowSum+=nums[i];
maxSum=windowSum;
for(int i=k;i<nums.size();i++) {
windowSum += nums[i]-nums[i-k]; // slide: add right, remove left
maxSum = max(maxSum, windowSum);
}
return maxSum;
}
// VARIABLE WINDOW — expand right, shrink left when invalid
// Template: find LONGEST window satisfying condition
int variableWindow(vector<int>& nums) {
int lo=0, res=0;
/* window state variables */
for(int hi=0; hi<nums.size(); hi++) {
/* add nums[hi] to window */
while(/* window invalid */) {
/* remove nums[lo] from window */
lo++;
}
res = max(res, hi-lo+1); // current valid window size
}
return res;
}
Interactive: Max Sum Fixed Window (k=3)
Array [2,1,5,1,3,2], window size k=3. Slide right by subtracting the outgoing element and adding the incoming one — O(1) per step instead of O(k).
Practice Problems
#3Longest Substring Without Repeating CharactersMedium
Find length of longest substring without repeating characters.
Pattern: Variable window. Expand right. When duplicate found, shrink left until no duplicates. Track char positions with hash map.
C++
int lengthOfLongestSubstring(string s) {
unordered_map<char,int> last; // char → last index seen
int lo=0, res=0;
for(int hi=0;hi<s.size();hi++) {
if(last.count(s[hi])) lo=max(lo, last[s[hi]]+1);
last[s[hi]]=hi;
res=max(res, hi-lo+1);
}
return res;
}
// Time: O(n) Space: O(1) — at most 128 ASCII chars
#121Best Time to Buy and Sell StockEasy
Buy once, sell once. Maximize profit. Must buy before selling.
Pattern: One-pass. Track minimum price seen so far (best buy). For each day, compute profit if sold today = price - minPrice.
C++
int maxProfit(vector<int>& prices) {
int minP=INT_MAX, maxProfit=0;
for(int p:prices) {
minP=min(minP,p);
maxProfit=max(maxProfit, p-minP);
}
return maxProfit;
}
// Time: O(n) Space: O(1)
#643Maximum Average Subarray IEasy
Find the contiguous subarray of length k with the maximum average value.
Pattern: Fixed window, the purest form. Compute the first window's sum, then slide: add the entering element, subtract the leaving one. Never recompute from scratch.
C++
double findMaxAverage(vector<int>& nums, int k) {
long sum=0;
for(int i=0;i<k;i++) sum+=nums[i];
long best=sum;
for(int i=k;i<nums.size();i++) {
sum += nums[i] - nums[i-k]; // slide: enter right, leave left
best = max(best, sum);
}
return (double)best / k;
}
// Time: O(n) Space: O(1)
#424Longest Repeating Character ReplacementMedium
Can replace up to k characters. Find longest window where all same letter after k replacements.
Pattern: Window is valid when (windowSize - maxFreqChar) ≤ k. Track maxFreq, never decrease it (key trick — only need to grow window for answer).
C++
int characterReplacement(string s, int k) {
int cnt[26]={}, maxF=0, lo=0, res=0;
for(int hi=0;hi<s.size();hi++) {
maxF=max(maxF, ++cnt[s[hi]-'A']);
if(hi-lo+1-maxF > k) cnt[s[lo++]-'A']--; // shrink
res=max(res, hi-lo+1);
}
return res;
}
// Time: O(n) Space: O(1)
#567Permutation in StringMedium
Return true if s2 contains a permutation of s1 as a substring.
Pattern: Fixed window of size len(s1). Track character counts. Window valid when all counts are 0 (balanced). Maintain "matches" counter for O(1) validity check.
C++
bool checkInclusion(string s1, string s2) {
int need[26]={};
for(char c:s1) need[c-'a']++;
int k=s1.size(), matches=0;
for(int i=0;i<26;i++) if(need[i]==0) matches++;
int window[26]={};
for(int i=0;i<s2.size();i++) {
int c=s2[i]-'a';
window[c]++;
if(window[c]==need[c]) matches++;
if(window[c]==need[c]+1) matches--;
if(i>=k) {
int l=s2[i-k]-'a';
if(window[l]==need[l]) matches--;
if(window[l]==need[l]+1) matches++;
window[l]--;
}
if(matches==26) return true;
}
return false;
}
// Time: O(n) Space: O(1)
#76Minimum Window SubstringHard
Find shortest substring of s that contains all characters of t (including duplicates).
Pattern: Variable window. Expand right until window has all chars. Then shrink left while still valid. Track best window seen.
C++
string minWindow(string s, string t) {
unordered_map<char,int> need;
for(char c:t) need[c]++;
int have=0, total=need.size(), lo=0;
int resL=-1, resR=-1, resLen=INT_MAX;
unordered_map<char,int> win;
for(int hi=0;hi<s.size();hi++) {
win[s[hi]]++;
if(need.count(s[hi])&&win[s[hi]]==need[s[hi]]) have++;
while(have==total) {
if(hi-lo+1<resLen) { resLen=hi-lo+1; resL=lo; resR=hi; }
win[s[lo]]--;
if(need.count(s[lo])&&win[s[lo]]<need[s[lo]]) have--;
lo++;
}
}
return resL==-1 ? "" : s.substr(resL, resLen);
}
// Time: O(s + t) Space: O(s + t)
#239Sliding Window MaximumHard
Return the maximum of every window of size k as it slides across the array.
Pattern: Window + monotonic deque. Keep indices of elements in decreasing value order; the front is always the window max. Pop the back while the new element is bigger (they can never be a max again), pop the front when it slides out of the window.
C++
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq; // indices, values decreasing
vector<int> res;
for(int i=0;i<nums.size();i++) {
if(!dq.empty() && dq.front()==i-k) dq.pop_front(); // left edge left the window
while(!dq.empty() && nums[dq.back()]<nums[i]) dq.pop_back(); // dominated
dq.push_back(i);
if(i>=k-1) res.push_back(nums[dq.front()]);
}
return res;
}
// Time: O(n) — each index pushed/popped once Space: O(k)
Window validity: The key to sliding window is knowing "when is the window valid?" and "when do I shrink?". Define this clearly first, then the code writes itself.
Deeper Understanding
🧠 Under the Hood — fixed vs variable window
A sliding window is two pointers with a running aggregate (sum, counts, max-frequency) maintained incrementally. The reason it beats recomputation is that entering and leaving elements update the aggregate in O(1) — the window never gets re-scanned. That only works when the aggregate is incrementally updatable: sums and counts are; "median of window" is not (that needs two heaps or an ordered set).
⚖️ When to Use / When NOT to Use
✅ Use when the problem says "contiguous subarray/substring" plus a constraint (at most K distinct, sum ≥ target, no repeats)
Contiguity is non-negotiable — the window IS a contiguous range.
✅ Use when window validity is monotone: growing can only break it, shrinking can only fix it
This is what makes the two-pointer chase correct — you never need to re-expand from an old position.
❌ Avoid when the subarray need not be contiguous (subsequence problems)
Instead: DP — LIS, LCS and friends are subsequence problems, a window can't represent gaps.
❌ Avoid when negative numbers break monotonicity of a sum constraint
Instead: prefix sums + hash map (#560 Subarray Sum Equals K) — with negatives, growing the window doesn't monotonically grow the sum.
🚫 Common Misconceptions
"Always shrink the left edge one step at a time"
In Longest Substring Without Repeats, storing each char's last index lets L jump directly past the duplicate — no incremental shrink loop needed.
"Nested while inside for means O(n²)"
L only moves forward, at most n times over the entire run. Total work is ≤ 2n pointer moves — amortized analysis, same argument as monotonic stack.
"Sliding window solves any subarray problem"
It needs monotone validity. "Exactly K distinct" is not monotone — solve it as atMost(K) − atMost(K−1), two monotone windows.
🎤 Interview Follow-ups
"How would you count subarrays with exactly K odd numbers?"
The at-most trick: count(exactly K) = count(atMost K) − count(atMost K−1). Each atMost is a standard shrinking window, and counting uses += (hi − lo + 1) per step.
"Walk me through the minimum-window template"
Expand hi unconditionally, update counts; while the window is valid, record the answer and shrink lo. The answer is recorded during the shrink phase for min-problems, during expansion for max-problems.
"Why does #424 never decrease maxFreq when shrinking?"
A stale (too large) maxFreq only makes the validity test conservative — the window just stops growing until a genuinely better window appears. Since we only need the maximum length ever seen, correctness is preserved and we save an O(26) rescan per step.