Sliding Window Technique
The Sliding Window technique maintains a dynamic contiguous range [l, r] over an array or string, expanding r and shrinking l monotonically to solve subarray and substring problems in O(n) time.
Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code
Sliding Window Technique
The Sliding Window technique maintains a contiguous subarray or substring [l, r] while moving r forward one element at a time and shrinking l whenever a constraint is violated (or satisfied). Because both l and r only move right, every element enters and leaves the window at most once, guaranteeing $O(n)$ time!
At a Glance
| Window Type | Mechanism | Classic Examples |
| :--- | :--- | :--- |
| Fixed-Size Window | Window always has size k; add a[r], remove a[r - k] | Max sum subarray of size k, anagram search |
| Variable-Size Window | Expand r, shrink l while invalid (or valid) | Longest substring without repeating chars, Minimum Window Substring |
| Monotonic Deque Window | Maintain decreasing/increasing deque of indices | Sliding Window Maximum (LeetCode 239) |
---
How It Works (Variable-Size Window Template)
l = 0
for r = 0 to n - 1:
add A[r] to window state
while window is invalid:
remove A[l] from window state
l += 1
update answer with [l, r]
Step-by-Step Trace (Longest Substring Without Repeating Characters on "abcabcbb")
r = 0..2:"abc"→ length3r = 3('a'duplicate): shrinklpast'a'→"bca"→ length3r = 4('b'duplicate): shrinklpast'b'→"cab"→ length3- Result:
3.
---
Complexity & Key Insights
- Negative Numbers Break Variable Sliding Window! If an array has negative numbers, shrinking
ldoes not monotonically decrease the subarray sum—use Prefix Sums + Hash Map (or Monotonic Deque on prefix sums) instead! atMost(K) - atMost(K - 1)Trick: Counting subarrays with exactlyKdistinct elements is hard directly, butcountAtMost(K)is a trivial $O(n)$ sliding window—andexact(K) = atMost(K) - atMost(K - 1)!
---
Practice Problems
Easy
1. Maximum Sum Subarray of Fixed Size $k$
Find the maximum sum of any contiguous subarray of length k.
Approach: Fixed-size sliding window: add a[r] and subtract a[r - k]. Time: $O(n)$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
long long maxSumSizeK(const std::vector<int>& a, int k) {
long long sum = 0, best = std::numeric_limits<long long>::min();
for (int r = 0; r < static_cast<int>(a.size()); ++r) {
sum += a[r];
if (r >= k) sum -= a[r - k];
if (r >= k - 1) best = std::max(best, sum);
}
return best;
}
int main() {
std::cout << maxSumSizeK({2, 1, 5, 1, 3, 2}, 3) << "\n"; // 9 (5+1+3)
return 0;
}
</details>
2. Longest Substring Without Repeating Characters (LeetCode 3)
Return the length of the longest substring with all unique characters.
Approach: Track lastPos[128] for ASCII characters; jump l = max(l, lastPos[c] + 1) whenever c reappears inside [l, r]. Time: $O(n)$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <array>
#include <iostream>
#include <string>
int lengthOfLongestSubstring(const std::string& s) {
std::array<int, 128> lastPos;
lastPos.fill(-1);
int best = 0;
for (int l = 0, r = 0; r < static_cast<int>(s.size()); ++r) {
unsigned char c = static_cast<unsigned char>(s[r]);
if (lastPos[c] >= l) l = lastPos[c] + 1;
lastPos[c] = r;
best = std::max(best, r - l + 1);
}
return best;
}
int main() {
std::cout << lengthOfLongestSubstring("abcabcbb") << " "
<< lengthOfLongestSubstring("pwwkew") << "\n"; // 3 3
return 0;
}
</details>
---
Intermediate
3. Longest Subarray with Sum $\le S$ (Non-Negative Elements)
Find the maximum length of a contiguous subarray of non-negative integers with sum at most S.
Approach: Expand r, shrink l while sum > S. Time: $O(n)$. Space: $O(1)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <vector>
int longestSubarrayAtMostS(const std::vector<int>& a, long long S) {
long long sum = 0;
int best = 0;
for (int l = 0, r = 0; r < static_cast<int>(a.size()); ++r) {
sum += a[r];
while (sum > S) sum -= a[l++];
best = std::max(best, r - l + 1);
}
return best;
}
int main() {
std::cout << longestSubarrayAtMostS({1, 2, 1, 0, 1, 1, 0}, 4) << "\n"; // 5
return 0;
}
</details>
4. Subarrays with Exactly $K$ Distinct Integers (LeetCode 992)
Count the number of contiguous subarrays containing exactly k distinct integers.
Approach: countAtMost(nums, k) - countAtMost(nums, k - 1). Inside countAtMost, for each right endpoint r, there are r - l + 1 valid subarrays ending at r. Time: $O(n)$. Space: $O(n)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <unordered_map>
#include <vector>
long long atMostK(const std::vector<int>& a, int k) {
if (k < 0) return 0;
std::unordered_map<int, int> freq;
long long ans = 0;
int distinct = 0;
for (int l = 0, r = 0; r < static_cast<int>(a.size()); ++r) {
if (++freq[a[r]] == 1) ++distinct;
while (distinct > k) {
if (--freq[a[l]] == 0) --distinct;
++l;
}
ans += (r - l + 1);
}
return ans;
}
long long subarraysWithKDistinct(const std::vector<int>& a, int k) {
return atMostK(a, k) - atMostK(a, k - 1);
}
int main() {
std::cout << subarraysWithKDistinct({1, 2, 1, 2, 3}, 2) << "\n"; // 7
return 0;
}
</details>
---
Hard
5. Sliding Window Maximum (Monotonic Deque, LeetCode 239)
Given an array nums and window size k, return the maximum value in every length-k window in $O(n)$ total time.
Approach: Maintain a std::deque<int> of indices whose values are strictly decreasing. Before pushing r, pop smaller elements from the back; pop expired indices <= r - k from the front. The front is always the window maximum! Time: $O(n)$. Space: $O(k)$.
<details>
<summary>Show C++ Solution</summary>
#include <deque>
#include <iostream>
#include <vector>
std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) {
std::deque<int> dq;
std::vector<int> res;
for (int r = 0; r < static_cast<int>(nums.size()); ++r) {
while (!dq.empty() && dq.front() <= r - k) dq.pop_front();
while (!dq.empty() && nums[dq.back()] <= nums[r]) dq.pop_back();
dq.push_back(r);
if (r >= k - 1) res.push_back(nums[dq.front()]);
}
return res;
}
int main() {
for (int x : maxSlidingWindow({1, 3, -1, -3, 5, 3, 6, 7}, 3)) std::cout << x << " ";
std::cout << "\n"; // 3 3 5 5 6 7
return 0;
}
</details>
---
Related Algorithms
- Two Pointers — broader monotonic pointer paradigm.
- Mo's Algorithm — reorders offline range queries so a sliding window answers them in $O((n + q)\sqrt{n})$.