Om's Brain

2. Sliding Window

15 min read

🔍 When Do You Reach For This?

You’re looking at a subarray / substring problem. You see:

“(Longest / Shortest / Number of) (Subarrays / Substrings) with (At most / Exactly / At least) K elements that fit (some condition)”

That’s the signal. Sliding window works because instead of re-computing from scratch every time, you reuse the previous window — only touching the one element entering and the one leaving.

Core idea: convert two nested loops → one loop. O(n²) → O(n).

Sliding Window only works when…

  • Moving the right pointer monotonically grows the window’s state,
  • and moving the left pointer monotonically shrinks it.
  • The moment a single element can both increase AND decrease the state — prefix sum is what you need.

1️⃣ Fixed Size Sliding Window

📌 Use when window size is constant (k)

Brute Force

// BF
// - No of windows = `n-k+1`
for (int i = 0; i < n - (k - 1); i++) {
    for (int j = i; j < i + k; j++) {
       // process window from i to i + k
    }
}

Pattern

  • Build first window of size k
  • Slide by:
    • add new element (right enters)
    • remove old element (left leaves)
    • update answer

Remember

No of windows = n - k + 1’ total subarray of any array = n*(n+1)/2

// Step 1: Build first window of size k
for (int i = 0; i < k; i++) {
	add(arr[i]);
}
 
// Use first window
update_answer();
 
// Step 2: Slide window
for (int i = k; i < n; i++) {
 
	// Add new element
	add(arr[i]);
 
	// Remove old element
	remove(arr[i - k]);
 
	// Update answer
	update_answer();
}

Example — Max Sum Subarray of Size k ⭐

int maxSubarraySum(vector<int>& arr, int k) {
    int n = arr.size();
 
    if (k > n) return -1;
 
    int windowSum = 0;
 
    // Step 1: Build first window of size k
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
 
    // Initialize result using first window
    int maxResult = windowSum;
 
    // Step 2: Slide window
    for (int i = k; i < n; i++) {
        // add new element to window
        windowSum += arr[i];
 
        // remove old element
        windowSum -= arr[i - k];
 
        // Update answer
        maxResult = max(maxResult, windowSum);
    }
 
    return maxResult;
}
 
// TC - `O(n)`
// SC - `O(1)`

2️⃣ Variable Size Sliding Window

📌 Use when window size is not fixed — expand and shrink based on a condition.

Pattern

  • Expand window using i (right pointer)
  • Add the new element into window
  • While invalid → shrink from j (left pointer) until valid again
  • Update answer

Remember

WinSize = i - j + 1

int j = 0;
 
for (int i = 0; i < n; i++) {
 
    // 1. Add new element in window
    add(arr[i]);
 
    // 2. Shrink from left while invalid
    while (invalid_window()) {
        remove(arr[j]);
        j++;
    }
 
    // 3. Use valid window
    update_answer();
}

Example — Longest Substring Without Repeating Characters

int lengthOfLongestSubstring(string s) {
	int j = 0, maxLen = 0;
	unordered_map<char, int> freq;
 
	// Step 1: Expand window
	for (int i = 0; i < s.size(); i++) {
		char c = s[i];
		freq[c]++;
 
		// Step 2: Shrink while invalid
		while (freq[c] > 1) {
			freq[s[j]]--;
			j++;
		}
 
		// Step 3: Update answer
		maxLen = max(maxLen, i - j + 1);
	}
 
	return maxLen;
}
 
// TC - `O(n)`
// SC - `O(k)` // k = unique chars

For questions

Total no of subarrays ending at i from j = i - j + 1

🧩 Pattern 1 — Length Questions (Max/Min Window)

These find the longest or shortest subarray/substring satisfying a condition.

Approach

The while loop shrinks until valid. Then j - i + 1 is the current valid window length.

update_answer = res = max(res, j - i + 1)   // longest
update_answer = res = min(res, j - i + 1)   // shortest

3. Longest Substring Without Repeating Characters Medium ⭐

State: frequency map of chars in window
Invalid: any char has count > 1

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> freq;
    int res = 0, j = 0;
    for (int i = 0; i < s.size(); i++) {
        freq[s[i]]++;
        while (freq[s[i]] > 1) {    // shrink until no duplicate
            freq[s[j++]]--;
        }
        res = max(res, i - j + 1);
    }
    return res;
}
// TC - `O(n)` | SC - `O(k)`

340. Longest Substring with At Most K Distinct Characters Hard ⭐

State: frequency map (freq.size() = distinct count)
Invalid: freq.size() > k

int lengthOfLongestSubstringKDistinct(string& s, int k) {
    unordered_map<char, int> freq;
    int res = 0, j = 0;
    for (int i = 0; i < s.size(); i++) {
        freq[s[i]]++;
        while (freq.size() > k) {
            freq[s[j]]--;
            if (freq[s[j]] == 0) freq.erase(s[j]);   // erase → size shrinks
            j++;
        }
        res = max(res, i - j + 1);
    }
    return res;
}
// TC - `O(n)` | SC - `O(k)`

1004. Max Consecutive Ones III Medium ⭐

Rephrased: longest subarray with at most K zeros
State: count of zeros in window
Invalid: zeros > K

int longestOnes(vector<int>& A, int K) {
    int zeros = 0, res = 0, j = 0;
    for (int i = 0; i < A.size(); i++) {
        if (A[i] == 0) zeros++;
        while (zeros > K) {
            if (A[j] == 0) zeros--;
            j++;
        }
        res = max(res, i - j + 1);
    }
    return res;
}
// TC - `O(n)` | SC - `O(1)`

904. Fruit Into Baskets Medium ⭐

Same as “at most 2 distinct numbers.”
State: frequency map (freq.size() = distinct count)
Invalid: freq.size() > 2

int totalFruit(vector<int>& a) {
    unordered_map<int, int> freq;
    int res = 0, j = 0;
    for (int i = 0; i < a.size(); i++) {
        freq[a[i]]++;
        while (freq.size() > 2) {
            freq[a[j]]--;
            if (freq[a[j]] == 0) freq.erase(a[j]);   // erase → size shrinks
            j++;
        }
        res = max(res, i - j + 1);
    }
    return res;
}
// TC - `O(n)` | SC - `O(1)`

424. Longest Repeating Character Replacement Medium 📍 🐢

Key insight: window is valid if (windowLen - maxFreq) <= k
(i.e., replacements needed ≤ k)
State: frequency map; recompute maxFreq from map each step
Invalid: (i - j + 1) - maxFreq > k

bool invalid(const unordered_map<char, int>& freq, int windowLen, int k) {
    int maxFreq = 0;
    for (auto& it : freq)
        if (it.second > maxFreq) maxFreq = it.second;
    return windowLen - maxFreq > k;
}
 
int characterReplacement(string s, int k) {
    unordered_map<char, int> freq;
    int res = 0, j = 0;
    for (int i = 0; i < s.size(); i++) {
        freq[s[i]]++;
 
        while (invalid(freq, i - j + 1, k)) {
            freq[s[j]]--;
            if (freq[s[j]] == 0) freq.erase(s[j]);
            j++;
        }
        res = max(res, i - j + 1);
    }
    return res;
}
// TC - `O(26n)` = `O(n)` | SC - `O(26)` = `O(1)`

Alternative Optimization

There is another way to optimize this to true instead of by keeping a global maxFreq and never decreasing it when the window shrinks. Watch NeetCode’s YouTube explanation for why this clever optimization works.

76. Minimum Window Substring Hard 📍 ⚠️

State: count map seeded with chars of t; remain = distinct chars of t not yet satisfied
Invalid when remain > 0 (window doesn’t contain all of t yet)
Shrink while valid (when remain == 0) to minimize

string minWindow(string s, string t) {
    unordered_map<char, int> count;
    for (char c : t) count[c]++;
    int remain = count.size();   // distinct chars still needed
    int minLen = INT_MAX, minStart = 0, j = 0;
 
    for (int i = 0; i < s.size(); i++) {
        count[s[i]]--;
        if (count[s[i]] == 0) remain--;   // this char is fully satisfied
 
        while (remain == 0) {             // window is valid → try to shrink
            if (i - j + 1 < minLen) {
                minLen = i - j + 1;
                minStart = j;
            }
            count[s[j]]++;
            if (count[s[j]] > 0) remain++;   // this char is no longer satisfied
            j++;
        }
    }
    return minLen == INT_MAX ? "" : s.substr(minStart, minLen);
}
// TC - `O(n + m)` | SC - `O(m)` where m = |t|

🧩 Pattern 2 — “Number of Subarrays” Questions

Before, we found min/max length. Now we count how many subarrays.

The Counting Trick

  • If [j..i] is valid, then ALL subarrays ending at i starting from j to i are valid too.
  • That’s i - j + 1 subarrays. So instead of res = max(...), do res += i - j + 1.
// At every step, if window [j..i] is valid:
res += i - j + 1;

Why? All subarrays [j,i], [j+1,i], [j+2,i], ..., [i,i] are valid → that’s i - j + 1 of them.

”Exactly K” → use “At Most K” trick

The At Most → Exactly Trick

exactly(K) = atMost(K) - atMost(K-1) This is the cleanest approach for “exactly K” counting problems.

int atMost(vector<int>& A, int K) {
    if (K < 0) return 0;
    int res = 0, j = 0;
    // ... window state ...
    for (int i = 0; i < A.size(); i++) {
        // add A[i] to state
        while (/* condition > K */) {
            // remove A[j] from state
            j++;
        }
        res += i - j + 1;   // count all valid subarrays ending at i
    }
    return res;
}

930. Binary Subarrays With Sum Medium

Count subarrays with exactly S ones.

int numSubarraysWithSum(vector<int>& A, int S) {
    return atMost(A, S) - atMost(A, S - 1);
}
 
int atMost(vector<int>& A, int S) {
    if (S < 0) return 0;
    int res = 0, sum = 0, j = 0;
    for (int i = 0; i < A.size(); i++) {
        sum += A[i];
        while (sum > S) { sum -= A[j++]; }
        res += i - j + 1;
    }
    return res;
}
// TC - `O(n)` | SC - `O(1)`

992. Subarrays with K Different Integers Hard 📍 💀

Count subarrays with exactly K distinct integers.

int subarraysWithKDistinct(vector<int>& A, int K) {
    return atMost(A, K) - atMost(A, K - 1);
}
 
int atMost(vector<int>& A, int K) {
    unordered_map<int, int> count;
    int res = 0, j = 0;
    for (int i = 0; i < A.size(); i++) {
        count[A[i]]++;
        if (count[A[i]] == 1) K--;
        while (K < 0) {
            count[A[j]]--;
            if (count[A[j]] == 0) K++;
            j++;
        }
        res += i - j + 1;
    }
    return res;
}
// TC - `O(n)` | SC - `O(n)`

1248. Count Number of Nice Subarrays Medium 📍 ⚠️

Count subarrays with exactly K odd numbers.

int numberOfSubarrays(vector<int>& nums, int k) {
    return atMost(nums, k) - atMost(nums, k - 1);
}
 
int atMost(vector<int>& A, int k) {
    int res = 0, odds = 0, j = 0;
    for (int i = 0; i < A.size(); i++) {
        odds += A[i] % 2;
        while (odds > k) {
            odds -= A[j++] % 2;
        }
        res += i - j + 1;
    }
    return res;
}
// TC - `O(n)` | SC - `O(1)`

1358. Number of Substrings Containing All Three Characters Medium 💀

Key insight: once the window at [j..i] is valid (has a, b, c), ALL extensions [j..i], [j..i+1], ... are also valid — so count n - i subarrays starting from the current left j.

int numberOfSubstrings(string s) {
    unordered_map<char, int> freq;
    int res = 0, j = 0;
    for (int i = 0; i < s.size(); i++) {
        freq[s[i]]++;
        while (freq.size() == 3) {   // while valid (has a, b, c), shrink to find minimum left
            res += s.size() - i;     // all extensions of current [j..i] are valid
            freq[s[j]]--;
            if (freq[s[j]] == 0) freq.erase(s[j]);
            j++;
        }
    }
    return res;
}
// TC - `O(n)` | SC - `O(1)`

🧩 Pattern 3 — Minimum Window (Shrink while valid)

Flip the while loop

  • For maximum window: shrink while invalid → while (invalid) { shrink; }
  • For minimum window: shrink while valid → while (valid) { update_ans; shrink; }

This is exactly what 76. Minimum Window Substring uses.

209. Minimum Size Subarray Sum Medium

State: running sum
Shrink while: sum >= target (window is valid → try to shrink it further)

int minSubArrayLen(int target, vector<int>& nums) {
    int sum = 0, res = INT_MAX, j = 0;
    for (int i = 0; i < nums.size(); i++) {
        sum += nums[i];
        while (sum >= target) {
            res = min(res, i - j + 1);
            sum -= nums[j++];
        }
    }
    return res == INT_MAX ? 0 : res;
}
// TC - `O(n)` | SC - `O(1)`

🧩 Pattern 4 — When Standard SW Doesn’t Work

❌ Case 1: Need max AND min of window simultaneously

Problem: Longest Continuous Subarray with Absolute Diff ≤ Limit Hard

You can’t do while (invalid) left++ because you don’t know if left is the max or min of the window.

Fix: Use monotonic deques — one for max (decreasing), one for min (increasing).

int longestSubarray(vector<int>& nums, int limit) {
    deque<int> maxQ, minQ;   // store indices
    int j = 0, res = 0;
    for (int i = 0; i < nums.size(); i++) {
        // maintain decreasing deque for max
        while (!maxQ.empty() && nums[maxQ.back()] < nums[i]) maxQ.pop_back();
        // maintain increasing deque for min
        while (!minQ.empty() && nums[minQ.back()] > nums[i]) minQ.pop_back();
        maxQ.push_back(i);
        minQ.push_back(i);
 
        while (nums[maxQ.front()] - nums[minQ.front()] > limit) {
            j++;
            if (maxQ.front() < j) maxQ.pop_front();
            if (minQ.front() < j) minQ.pop_front();
        }
        res = max(res, i - j + 1);
    }
    return res;
}
// TC - `O(n)` | SC - `O(n)`

Monotonic Deque pattern

Whenever you need the running max or min of a sliding window → use a deque. Also see: 239. Sliding Window Maximum

❌ Case 2: Elements can be negative (state not monotonic)

Problem: 560. Subarray Sum Equals K — with negative numbers

Adding an element can decrease the sum. Removing can increase it. The standard while (invalid) loop breaks because moving j right doesn’t guarantee the window becomes valid.

Fix: Use Prefix Sum + HashMap.

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> mp;
    mp[0] = 1;
    int psum = 0, count = 0;
    for (int i = 0; i < nums.size(); i++) {
        psum += nums[i];
        count += mp[psum - k];   // how many times (psum - k) appeared before
        mp[psum]++;
    }
    return count;
}
// TC - `O(n)` | SC - `O(n)`

❌ Case 3: Palindrome / symmetric structure

Problem: 5. Longest Palindromic Substring

Palindromes don’t have a monotonic window property.

  • Adding a char on the right doesn’t tell you if the window is still a palindrome.
  • Moving left doesn’t fix a broken palindrome in a predictable way.

Fix: Expand from center — try every center point, expand both left and right.

🧩 Pattern 5 — Sliding Window Maximum (Monotonic Deque)

239. Sliding Window Maximum Hard

For each fixed window of size k, find the maximum.
Key: keep a decreasing deque of indices. Front is always the max of current window.

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;   // stores indices, front = max
    vector<int> res;
    for (int i = 0; i < nums.size(); i++) {
        // remove elements out of window
        while (!dq.empty() && dq.front() < i - k + 1)
            dq.pop_front();
        // maintain decreasing order
        while (!dq.empty() && nums[dq.back()] < nums[i])
            dq.pop_back();
        dq.push_back(i);
        // window is full
        if (i >= k - 1)
            res.push_back(nums[dq.front()]);
    }
    return res;
}
// TC - `O(n)` | SC - `O(k)`

🗺️ How to Identify the Sub-Pattern

Subarray / Substring problem?
├── Fixed window size k?
│   └── YES → Fixed Sliding Window
│
└── Variable window
    │
    ├── All elements positive / binary?
    │   │
    │   ├── Max LENGTH     → shrink while invalid, res = max(res, i-j+1)
    │   ├── Min LENGTH     → shrink while valid, update inside while
    │   └── COUNT subarrays
    │        ├── At most K  → res += i - j + 1
    │        └── Exactly K  → atMost(K) - atMost(K-1)
    │
    └── Negative elements possible?
        ├── Count / Length  → Prefix Sum + HashMap
        └── Divisibility   → Prefix Sum + Remainder map

Quick Decision Table

Problem asksTemplate
Max length, at most Kshrink while invalid → res = max(len)
Min length, at least Kshrink while valid → res = min(len)
Count, at most Kres += i - j + 1
Count, exactly KatMost(K) - atMost(K-1)
Need window max/minMonotonic Deque
Negative numbersPrefix Sum + HashMap
Divisibility (mod k)Prefix Sum + Remainder map
PalindromeExpand from center

🧠 Master Cheatsheet

Fixed Window

// Step 1: Build first window
for (int i = 0; i < k; i++) add(arr[i]);
update_answer();
 
// Step 2: Slide
for (int i = k; i < n; i++) {
    add(arr[i]);
    remove(arr[i - k]);
    update_answer();
}

Variable Window — Max Length

int j = 0;
for (int i = 0; i < n; i++) {
    add(arr[i]);
    while (invalid_window()) { remove(arr[j]); j++; }
    res = max(res, i - j + 1);
}

Variable Window — Min Length

int j = 0;
for (int i = 0; i < n; i++) {
    add(arr[i]);
    while (valid_window()) {
        res = min(res, i - j + 1);
        remove(arr[j]); j++;
    }
}

Count — At Most K

int atMost(vector<int>& A, int K) {
    int res = 0, j = 0;
    // ... state ...
    for (int i = 0; i < n; i++) {
        // add A[i]
        while (/* state > K */) { /* remove A[j] */ j++; }
        res += i - j + 1;
    }
    return res;
}

Count — Exactly K

return atMost(A, K) - atMost(A, K - 1);

State Tracker Decision

What to trackData structure
Sumsingle int
Char frequenciesint[26] or unordered_map<char,int>
Distinct countint + frequency map
Window max / minmonotonic deque<int>
Running max onlysingle int maxCount

Pattern Recognition

Signal in problemPattern
Longest/Shortest subarray with at most K of somethingVariable SW, shrink while invalid
Exactly K of somethingatMost(K) - atMost(K-1)
All chars of t must appear in windowMinimum Window (shrink while valid)
Need max of each windowMonotonic Deque
Negative numbers in arrayPrefix Sum + HashMap
Palindrome structureExpand from center
Fixed window, slide acrossFixed SW template

3 items under this folder.

Mindmap

Graph View

Backlinks