Overview
Many problems ask for the best contiguous subarray or substring that satisfies a condition. Checking every one is O(n²) or worse. A sliding window keeps a single range [left, right], grows it by moving right, and shrinks it by moving left whenever the condition breaks. Because each element enters and leaves the window at most once, the total work is O(n).
The art is choosing the window state: a running sum, a count of each character, the number of distinct values. The state must be cheap to update when one element enters or leaves. If you can do that, the problem is probably a sliding window.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| All subarrays, brute force | O(n²) windows, often O(n³) total |
| Sliding window | O(n) time |
| Window with frequency map | O(n) time, O(alphabet) space |
Patterns to recognise
Fixed window
Use it for: Problems that say "subarray of size k".
Pre-fill k elements, then slide one step at a time.
Longest valid window
Use it for: Longest substring without repeats, with at most k replacements, fruit into baskets.
Expand; shrink only until valid again; record right − left + 1.
Shortest covering window
Use it for: Minimum window substring, minimum size subarray sum.
Expand until valid; then shrink as far as possible while recording the length.
Code template
def length_of_longest_substring(s):
last_seen = {}
left = best = 0
for right, ch in enumerate(s):
if ch in last_seen and last_seen[ch] >= left:
left = last_seen[ch] + 1 # jump past the repeat
last_seen[ch] = right
best = max(best, right - left + 1)
return best
int lengthOfLongestSubstring(const string& s) {
array<int, 256> lastSeen;
lastSeen.fill(-1);
int left = 0, best = 0;
for (int right = 0; right < (int)s.size(); ++right) {
unsigned char ch = s[right];
if (lastSeen[ch] >= left) left = lastSeen[ch] + 1;
lastSeen[ch] = right;
best = max(best, right - left + 1);
}
return best;
}
Common mistakes
- Forgetting to update the window state when the left edge moves.
- Window length is right − left + 1, not right − left.
- Applying a shrinking window to arrays with negative numbers.
Quick check
Three questions on Sliding Window. Get all three right to earn +15 XP.
-
A sliding window turns many O(n x k) brute-force scans into:
Each element enters the window once and leaves once.
-
In a variable-size window, when do you move the left edge forward?
Expand right to explore, shrink left until the window is valid again.
-
Why can a sliding window fail on "subarray sum equals k" when numbers can be negative?
The technique relies on a monotonic change. Use prefix sums with a hash map instead.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Maximum Average Subarray ILeetCode Easy +20
- Longest Substring Without Repeating CharactersLeetCode Medium +40
- Longest Repeating Character ReplacementLeetCode Medium +40
- Permutation in StringLeetCode Medium +40
- Minimum Size Subarray SumLeetCode Medium +40
- Fruit Into BasketsLeetCode Medium +40
- Minimum Window SubstringLeetCode Hard +70
- Subarrays with K Different IntegersLeetCode Hard +70
Stuck on Sliding Window?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor