Coding Interview: Patterns & DSA · Arrays & Strings · Lesson 2 of 3
The sliding-window pattern
A sliding window is a two-pointer variant for problems about contiguous subarrays or substrings. You expand a window by moving its right edge, and contract it from the left when it violates a constraint — so each element enters and leaves the window at most once, giving O(n).
- Fixed-size window: slide a window of length
k, adding the new element and removing the old one each step (e.g. max average of anykconsecutive elements). - Variable-size window: grow the right edge, and shrink the left while a condition is broken, tracking the best window seen.
Example: longest substring without repeating characters
Keep a set of characters currently in the window. Advance right; if the new character is already in the set, shrink from left until it is not. The answer is the largest window width reached.
def longest_unique(s): seen = set() left = best = 0 for right in range(len(s)): while s[right] in seen: seen.remove(s[left]) # shrink from the left left += 1 seen.add(s[right]) best = max(best, right - left + 1) return best
Do not restart the windowThe whole point is that
left never moves backward. If you recompute the window from scratch on each violation you are back to O(n^2). Slide, do not restart.Recognize itSliding window fits problems asking for the longest / shortest / count of a contiguous subarray or substring satisfying a constraint (at most K distinct, sum >= target, no repeats).
◆ Lock it in
- Sliding window solves contiguous subarray/substring problems in
O(n). - Expand right, contract left on a violation — each element enters/leaves once.
- Both pointers only move forward; restarting the window kills the speedup.
Feynman drill — say it out loudExplain why a sliding window is O(n) even though it has a nested while-loop inside the for-loop.
Step 1 rate your confidence · Step 2 pick your answer
What guarantees a sliding-window solution runs in O(n) despite the inner while-loop?
Step 1 — how sure are you?