Sliding Window¶
Also known as: Window, Caterpillar Method, Two Pointers (Same Direction)
A window (a contiguous stretch) slides along the data. You extend the right edge to grow it and pull the left edge in to shrink it, keeping some running summary — a sum, a count, a character tally — updated as you go. Because each element enters once and leaves at most once, the whole thing runs in linear time even though it feels like nested loops.
Before you start¶
- Two Pointers (this pattern is the same-direction variant with a maintained window)- Comfortable using a hash map / dictionary for character counts in your language.
What 'solved properly' looks like
Target: O(n) time, O(k) space (where k is the window size or alphabet size). If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
You maintain two pointers that both move left to right. The space between them is the "window" — a contiguous segment of the data that satisfies some condition. You extend the right edge to include new elements, and when the condition breaks, you advance the left edge until it's satisfied again. A running total or frequency map travels with the window, updating by removing the left element and adding the right one, so you never re-scan the window from scratch.
Why it matters: It converts the classic O(n²) "check every subarray" brute force into a single O(n) pass, and it's the single most common Medium-interview pattern. Subarray sums, longest valid substrings, and fixed-size averages all collapse into the same structure once you see the window shape.
When to reach for it¶
Reach for it when the problem asks for something about a contiguous subarray or substring — the longest, shortest, maximum, minimum of something "such that" a condition holds, a fixed window of size k, "at most K distinct" elements, or "without repeating characters." If the problem uses any of those phrases, a sliding window is the first thing to try.
When not to use it
Contiguity is mandatory. If the problem allows skipping elements, it's a subsequence problem and this pattern won't work — the replacement technique depends on the problem (greedy, two pointers, dynamic programming, or other approaches). Also check that the shrink condition is monotonic: the classic trap is a "sum ≥ target" problem where the array contains negative numbers, which breaks the assumption that shrinking the window always reduces the sum. Check the constraints for positives before reaching for it.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Best Time to Buy and Sell Stock | LeetCode | Easy | 15 mins | teaching |
| 2 | Maximum Average Subarray I | LeetCode | Easy | 15 mins | teaching |
| 3 | Longest Substring Without Repeating Characters | LeetCode | Medium | 25 mins | consolidation |
| 4 | Minimum Size Subarray Sum | LeetCode | Medium | 25 mins | consolidation |
| 5 | Longest Repeating Character Replacement | LeetCode | Medium | 30 mins | challenge |
Already know this? Test out.
If you can solve Longest Repeating Character Replacement cleanly in one sitting — managing the character frequency map and knowing exactly when to shrink the window — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.