CONCEPT · 60 minutes
Reduce O(n^2) brute-force loops to O(n) with converging pointers and shrinking windows. The essential patterns for substring and subarray problems.
The first time I needed to find the longest span of clean log lines — where "clean" meant no error code in the line — I wrote the obvious double loop. Outer loop picks a start position. Inner loop extends as far as it can. Record the longest. It was correct. It was also O(n^2) on a log file with a hundred thousand lines, and it was visibly slow.
The fix I reached for was a window. Instead of restarting from a new position each time the constraint broke, I slid the left boundary forward until the constraint was satisfied again, then kept growing the right boundary. The window never contracted past its left edge, so every element was visited at most twice. O(n) total.
That is the core insight of this module: there is a class of problems where a "restart from scratch" nested loop is O(n^2), and a "slide the boundary" approach is O(n), and the two produce identical results. Recognising that class is the skill; the mechanics follow quickly.
There are two distinct techniques to learn here. Two pointers uses indices that converge inward from opposite ends, or chase each other from left to right. Sliding window maintains a contiguous range [left, right] and grows or shrinks it based on a constraint. They share the same underlying logic — move a pointer in one direction and never backtrack — but are the right tool in different situations.
Connection to previous modules: the variable sliding window almost always needs a frequency map inside it. When the constraint is "at most k distinct characters," you need a Counter or defaultdict tracking the window's contents as you expand and shrink. The frequency map patterns from module 02 apply directly here.
The two-pointer technique uses exactly two indices into the same array. The key design decision is which direction each pointer moves.
The opposite-end pattern starts left at index 0 and right at index n - 1, then moves them inward. It works correctly only when the array is sorted — that is the precondition that makes it safe to say "this sum is too large, so I can move right left without missing any valid pairs."
Analogy: Picture two people walking toward each other on a number line. The left person only steps right; the right person only steps left. They can only "pass" each other if the answer doesn't exist. Every step eliminates a cell of the search space, giving O(n) instead of O(n^2).
The sorted precondition bites people here: both Two Sum II and Valid Palindrome look similar because they converge from both ends. But Valid Palindrome works on any string — the alphanumeric filter does not require sorting. Two Sum II only works because the array is already sorted. If you apply opposite-end pointers to an unsorted Two Sum, the algorithm terminates without exploring all pairs.
Same-direction pointers both start at the left and move right, but at different speeds. The slow pointer writes keepers; the fast pointer reads every element.
The in-place guarantee is O(1) extra space. The slow/fast framing generalises: "Move Zeroes", "Remove Element", and "Remove Duplicates II" all use the same pattern with a slightly different keeper condition.
sequenceDiagram
participant F as fast (reads)
participant S as slow (writes)
Note over F,S: [1, 1, 2, 3, 3]
F->>S: nums[1]=1 == nums[0]=1 — skip
F->>S: nums[2]=2 != nums[0]=1 — slow++ then write
Note over S: slow=1, writes 2
F->>S: nums[3]=3 != nums[1]=2 — slow++ then write
Note over S: slow=2, writes 3
F->>S: nums[4]=3 == nums[2]=3 — skip
Note over F,S: Result prefix: [1, 2, 3], length=3The sliding window maintains a contiguous subarray nums[left..right] and slides it rightward. The right pointer always advances. The left pointer advances only when the window violates a constraint.
If the problem says "exactly k elements" or "window of size k," the width never changes.
Most substring problems use a variable window. The right pointer always advances. The left pointer advances when the window becomes invalid (too many distinct characters, sum too large, etc.).
The template is always the same shape; only the "is the window valid?" condition changes.
The window shrink is a while loop, not an if. After adding s[right], you may need to remove multiple left elements before the window is valid again. An if only removes one; a while removes as many as needed. This is a common off-by-one error in first implementations.
graph LR
subgraph "s = 'a b c a b c b b'"
A0["a"]
A1["b"]
A2["c"]
A3["a"]
A4["b"]
A5["c"]
A6["b"]
A7["b"]
end
subgraph "Window grows then shrinks"
W1["[a b c] len=3"]
W2["a violates → shrink → [b c a] len=3"]
W3["b violates → shrink → [c a b] len=3"]
W4["c violates → shrink → [a b c] len=3"]
W5["b violates → shrink → [c b] len=2"]
W6["b violates → shrink → [b] len=1"]
end
W1 --> W2 --> W3 --> W4 --> W5 --> W6When the variable window bites: the while shrink loop looks like a nested O(n) inside an O(n) outer loop, which would be O(n^2). It isn't. The left pointer never moves left — it only advances. Across the entire algorithm, left moves at most n times total, regardless of how many times the inner while triggers. Every element enters and exits the window exactly once: 2n total pointer movements, so O(n) overall. You must convince yourself of this before you trust the algorithm.
Try these from memory before moving on:
nums[i] and removing nums[i - k]. Why is it safe to index i - k without going negative?left never exceed right?Reflective prompt: The sliding window visits each element at most twice — once when the right pointer adds it, once when the left pointer removes it. Compare this to the brute-force double loop, where the inner loop revisits elements the outer loop already passed. What property of the problem makes this "no need to backtrack" guarantee safe? And what happens to that guarantee if the array is not a contiguous memory structure — say, a linked list?
Problem: Minimum Window Substring
Given strings s and t, return the minimum window in s that contains all characters of t. If no such window exists, return "". The window must contain every character of t including duplicates.
Examples:
s = "ADOBECODEBANC", t = "ABC" → "BANC"s = "a", t = "a" → "a"s = "a", t = "aa" → "" (can't satisfy two 'a's)This is the classic "hard" sliding window — it combines everything: a variable window, a frequency map for the target, and a second frequency map for the window.
Hint 1: You need two frequency maps: t_count (built once from t, never changes) and window_count (updated as you expand and shrink). The window is "valid" when every character in t_count appears at least as many times in the window.
Hint 2: The formed counter tracks how many distinct characters in t are currently satisfied (window frequency >= target frequency). When formed == len(t_count), the window is valid. Shrink from the left while it remains valid.
Hint 3: Track the best window as (length, left_index, right_index). After the loop, reconstruct with s[best_left : best_right + 1].
Why minimum window substring is worth studying: it is the hardest common sliding window problem, and once you can write it comfortably the rest of the pattern family feels easy. The key realization is that the while shrink loop is safe — it can only run as many total times as right advanced, so the outer+inner combined is still O(n).
Application-level questions on two-pointer and sliding-window patterns
1. The opposite-end two-pointer pattern on a Two Sum problem requires the input array to be what?
Correct Answer: B
The opposite-end pattern works because, on a sorted array, if the sum is too large you can safely move the right pointer left (reducing the sum), and if too small move the left pointer right (increasing it). Without sorting this monotone property doesn't hold and moving a pointer gives no information.
2. In a variable-size sliding window, when do you shrink the window (move the left pointer)?
Correct Answer: B
You shrink (move left) exactly when the current window violates the constraint — e.g., when it contains a repeated character or the sum exceeds k. You keep shrinking until the constraint is satisfied again, then record the window size if it's a new maximum.
3. Which problem type calls for a FIXED-size sliding window rather than a variable one?
Correct Answer: B
A fixed-size window has a predetermined width k — you slide a k-wide frame across the array. A variable window expands until the constraint is violated, then shrinks. 'Exactly k elements' is the canonical fixed-size signal; 'longest/shortest with constraint' signals a variable window.
4. You need to remove all occurrences of val from nums in-place and return the new length. Which pointer pattern fits?
Correct Answer: B
Same-direction (slow/fast) pointers: the fast pointer reads every element; the slow pointer only advances when a keeper element is found, writing it to the slow position. This compacts in-place in O(n) with O(1) extra space. Opposite-end pointers would work too but require special handling for the order of elements.
5. A sliding window visits each element at most twice (once when the right pointer adds it, once when the left pointer removes it). What is the time complexity?
Correct Answer: C
Each of the n elements is added once and removed at most once — at most 2n total pointer movements. That makes the algorithm O(n), even though it looks like two nested loops (one for right, one for left). The inner while loop doesn't multiply with the outer for loop because left never exceeds right.