Notes › DSA
Sliding Window
When a problem asks about a contiguous subarray or substring — "longest", "shortest", "maximum sum of size k", "at most k distinct" — a sliding window usually turns an O(n²) or O(n³) brute force into O(n).
The window is the range [left, right]. Instead of recomputing everything for every range, you add the element entering on the right and remove the one leaving on the left.
Type 1: fixed-size window
Maximum sum of any subarray of size k.
int maxSumK(vector<int>& a, int k) {
int sum = 0;
for (int i = 0; i < k; i++) sum += a[i];
int best = sum;
for (int r = k; r < a.size(); r++) {
sum += a[r] - a[r - k]; // add new, remove old
best = max(best, sum);
}
return best;
}
Type 2: variable-size window
Grow the window with right; while the window breaks the rule, shrink it with left.
Template
int left = 0, best = 0;
for (int right = 0; right < n; right++) {
add(a[right]); // expand
while (windowIsInvalid()) { // shrink until valid again
remove(a[left]);
left++;
}
best = max(best, right - left + 1);
}
Longest substring without repeating characters
int lengthOfLongestSubstring(string s) {
vector<int> cnt(256, 0);
int left = 0, best = 0;
for (int right = 0; right < s.size(); right++) {
cnt[s[right]]++;
while (cnt[s[right]] > 1) cnt[s[left++]]--;
best = max(best, right - left + 1);
}
return best;
}
Smallest subarray with sum ≥ target (positive numbers)
int minSubArrayLen(int target, vector<int>& a) {
int left = 0, sum = 0, best = INT_MAX;
for (int right = 0; right < a.size(); right++) {
sum += a[right];
while (sum >= target) {
best = min(best, right - left + 1);
sum -= a[left++];
}
}
return best == INT_MAX ? 0 : best;
}
Longest vs shortest
| Asked | Update the answer… |
|---|---|
| Longest valid window | after shrinking (the window is valid again) |
| Shortest valid window | inside the shrinking loop (while it is still valid) |
"Exactly K" trick
Count of subarrays with exactly K distinct = atMost(K) − atMost(K − 1), where atMost is a normal variable window.
When the window does NOT work
The window needs this property: making the window bigger never makes it "more valid" in the wrong direction (monotonic). With negative numbers, "sum ≥ target" is no longer monotonic — use prefix sum + hash map instead (see the Hashing note).
Sliding window maximum (monotonic deque)
Keep indices in a deque with decreasing values; the front is the maximum of the current window. O(n).
vector<int> maxSlidingWindow(vector<int>& a, int k) {
deque<int> dq; vector<int> ans;
for (int i = 0; i < a.size(); i++) {
if (!dq.empty() && dq.front() == i - k) dq.pop_front(); // out of the window
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back(); // smaller ones are useless
dq.push_back(i);
if (i >= k - 1) ans.push_back(a[dq.front()]);
}
return ans;
}
Classic problems
| Problem | Window |
|---|---|
| Max sum subarray of size K | fixed |
| Longest substring without repeating characters | variable + map |
| Longest substring with at most K distinct characters | variable + map |
| Minimum size subarray sum | variable (shortest) |
| Permutation in string / find all anagrams | fixed + count array |
| Minimum window substring | variable (shortest) + counts |
| Fruits into baskets / max consecutive ones III | variable |
| Sliding window maximum | fixed + deque |
Practise them in the Sliding Window section.
Interview one-liners
- Signal words: contiguous, subarray, substring, window, longest/shortest with a condition.
- Each element enters and leaves the window once → O(n) even with the inner
while. - Explain why shrinking is safe: once a window is invalid, every bigger window with the same left end is also invalid.