The Core Idea
One Window, Moving Across the Data
A brute-force solution to 'find something about every contiguous chunk of size k' typically re-scans each chunk from scratch — for each of n possible starting positions, scanning k elements, giving O(n × k). The sliding window technique instead maintains a running window as a single contiguous 'view' into the array, updating it incrementally: add the new element entering the window, remove the old element leaving it, rather than rescanning everything.
This works because moving the window by one position only changes two elements — one leaves, one enters — so the update cost per shift is O(1) instead of O(k), collapsing the total complexity to O(n) regardless of the window size k.
💡 Memory Trick
Picture a physical window frame sliding along a long mural on a wall. You don't repaint or re-photograph the entire visible section every time you nudge the frame — you just notice what new sliver of mural appeared on the right edge and what sliver disappeared off the left edge. The running total (sum, count, or whatever you're tracking) only needs to adjust for those two slivers, not the whole frame's contents.
The Two Window Types
Fixed-Size vs. Variable-Size Windows
1
Fixed-Size Window
The window always covers exactly k elements. Slide it one position at a time: subtract the element leaving on the left, add the element entering on the right, and update your running answer (sum, max, count, etc.) in O(1) per slide.
Example: finding the maximum sum of any 5 consecutive elements in an array — maintain a running sum, subtract the outgoing element and add the incoming one at each step.
2
Variable-Size Window
The window grows and shrinks based on a condition. Typically you expand the right edge until the window violates some constraint, then shrink the left edge until it's valid again, tracking the best window size seen along the way. This handles problems where the 'right' window size isn't known in advance.
Example: finding the longest substring without repeating characters — expand right until a repeat is found, then shrink left past the first occurrence of that repeated character.
Why It's Fast
Amortized O(n) Despite Nested-Looking Logic
Variable-size window code often looks like it has two nested loops (an outer loop expanding right, an inner loop shrinking left), which might suggest O(n²). But because the left pointer only ever moves forward and never resets, it can move at most n times total across the entire algorithm's run — not n times per outer-loop iteration. This means the total work across both pointers combined is O(n), not O(n²), even though the code has a nested-loop shape.
This technique is the backbone of a large family of substring and subarray problems: maximum sum subarray of fixed size, longest substring with at most k distinct characters, minimum window substring containing all characters of a target string, and longest subarray with sum less than or equal to a target.
🖥️ Applied Scenario
You're analyzing a stream of daily website traffic numbers and need to find the maximum total traffic across any 7-day rolling window.
1
You compute the sum of the first 7 days as your initial window sum, and set that as your current maximum.
2
You slide the window forward one day at a time: subtract the day leaving the window (day 1) and add the day entering it (day 8), updating the sum in constant time rather than re-summing all 7 days.
3
You compare each new window sum to your running maximum, updating it whenever a higher 7-day total appears.
4
Conclusion: you scan the entire traffic history in a single O(n) pass, instead of the O(n × 7) a naive re-sum-every-window approach would require.
📌 Exam Application
Exam questions often present a brute-force nested-loop solution to a subarray or substring problem and ask you to optimize it — the expected answer identifies that a sliding window applies whenever the problem involves a contiguous range and a condition that can be checked incrementally. You may also be asked to explain why a seemingly nested-loop sliding window solution is actually O(n), which requires explaining that the inner pointer never resets and moves at most n times total.
⚠️ Most Common Sliding Window Technique Mistakes
The most common mistake is recomputing the window's sum, max, or count from scratch on every slide instead of updating it incrementally — this silently turns an intended O(n) solution back into O(n × k), defeating the entire purpose of the technique. Another frequent error in variable-size window problems is forgetting to shrink the left pointer at all when a constraint is violated, causing the window to grow without bound and produce incorrect results.
✓ Quick Self-Test
Can you explain why a variable-size sliding window is O(n) overall, even though the code has a nested-loop shape? Can you trace through finding the maximum sum of any 3 consecutive elements in a small array, showing the running sum update at each slide?
Next Lesson
Recursion vs Iteration
→
← All Algorithms Lessons