Unit 1.7 · about 5 h
94 / 324Two pointers and sliding windows
Two pointers and windows replace nested loops with single passes wherever order or monotonicity lets one pointer's move settle another's. Recognizing the precondition is the skill.
- derive
- implement
You can now
- State the ordering or monotonicity precondition before moving a pointer.
- Implement opposite-ends, same-direction, fixed and variable windows with shrink triggers.
- Construct the negative-numbers counterexample that breaks shrinking windows.
Covers
- Two-pointer invariants and ordering assumptions
- Fixed and variable windows and monotonicity
Study, in this order
4 steps
- Two pointers: opposite endsDSA Handbook - Foundations and linear patterns
Why the proof actually works - the shorter-wall case analysis; The four primitives; Worked example LC 11 on
[1, 8, 6, 2, 5, 4, 8, 3, 7]; Worked example LC 15 with the three duplicate-skips; What it actually costs - Two pointers: same directionDSA Handbook - Foundations and linear patterns
The four primitives (seed, scan, keep, commit); Worked example LC 26 on
[1, 1, 2, 2, 3]; When the pattern bends (tail-fill LC 283, three-way partition LC 75, backward merge LC 88) - Sliding window: fixed sizeDSA Handbook - Foundations and linear patterns
The pattern (build-first-window then slide); The four primitives; Worked example LC 643 on
[2, 1, 5, 1, 3, 2, 1, 4]withk = 3; Frequency-map slide with the matched counter (LC 567) - Sliding window: variable sizeDSA Handbook - Foundations and linear patterns
The pattern (expand right, shrink while broken); The four primitives plus the shrink trigger; Worked example LC 3 on
pwwkew; Last-index jump;have == requiredfor LC 76
Focus on
- Opposite ends needs sortedness or an equivalent extremum argument; the shorter-wall move is proved by case analysis.
- Variable windows need a monotone shrink trigger: all-nonnegative numbers for sums, distinctness for longest-substring.
- Last-index jumps and matched counters keep \(O(1)\) per step; rescanning the window on each slide is the \(O(nk)\) trap.
- Negatives break shrinking: the fix is prefix sums, next unit.
Reproduce closed-book
abc up to length 12 (derandomize, max_examples=300) in Python 3.13: expect 1 passed. Then exhibit [1, -1, 1, 1] seeking the shortest subarray with sum at least 2: the shrink loop reports length 4 and misses the tail [1, 1] of length 2.Traps
- Forgetting to sort for opposite-ends moves, or sorting when the original indices are the answer.
- Half-open confusion: an inclusive \([l, r]\) window changes the shrink condition and the length formula versus \([l, r)\).
- Counters with stale zero entries: membership tests see dead keys unless counts are deleted or a have-counter is maintained.
Practice
LeetCode 167: Two Sum II - Input Array Is Sorted
Implement the opposite-ends move with the sortedness precondition stated in a comment. Judge with the Examples [2, 7, 11, 15] target 9 and [2, 3, 4] target 6.
After submitting, compare against the handbook two-pointers-opposite section The four primitives.
LeetCode 3: Longest Substring Without Repeating Characters
Attempt cold with hidden tags. Implement the variable window with last-seen jumps. Judge with the Examples abcabcbb, bbbbb and pwwkew.
After submitting, read the AlgoMaster Longest Substring write-up (https://algomaster.io/learn/dsa/longest-substring-without-repeating-characters) and the handbook variable-window worked example on pwwkew.
Self-test
-
Prove the Container move: why advance the shorter wall?
Area is width times the shorter wall. Moving the taller wall cannot raise the minimum and shrinks the width; only moving the shorter wall can find a taller bound. Case analysis over where the optimum sits. -
Why does the Two Sum II move rule fail on unsorted input?
The rule (sum too small: advance left) assumes everything left of right is no larger. Unsorted input breaks the ordering the rule reads. -
Trace the negatives counterexample
[1, -1, 1, 1]with target sum at least 2.Running sums are 1, 0, 1, 2. The shrink loop first fires at the last element and reports length 4. Dropping the leading 1 leaves sum 1, so the loop stops before it drops the -1, which would raise the sum back to 2 at length 2. Shrinking assumes that removing an element never raises the sum, and a negative element breaks that. -
Why do the three 3Sum duplicate skips matter?
Without skipping equal outer values and equal left and right values, each duplicate occurrence re-emits the same triple: correct values with wrong multiplicity and wasted output.
Completion criterion
Stop when
Both are accepted cold with the invariant stated first, and your negatives trace shows exactly which shrink step discards the optimum.
Mark passed, then open 1.8 Only mark this when you can do it without notes.Leads to
- 1.8 Prefix sums, difference arrays and prefix plus hash When the numbers can be negative, prefix sums replace shrinking windows.
- 1.6 Stacks, queues, deques and monotone structures Trapping Rain Water meets both windows and monotone stacks.
Comes after
- 1.3 Loop invariants, brute-force oracles and differential testsWindow algorithms are the first invariants you will state before coding.
- 1.6 Stacks, queues, deques and monotone structuresSliding windows reuse the deque discipline with a different trigger.
Resources for this unit
- DSA Handbook - Foundations and linear patterns Study Part 0, Part 1, Part 3 and Part 4 in order, plus the Part 5 Linked-list fundamentals chapter. Use the routing-rule pages for arrays versus lists, map choice, stack versus queue, two pointers, sliding windows and prefix methods before seeing solved code.
Also in this section
- AlgoMaster DSA - linear structures slice Attempt Design HashMap, Longest Substring Without Repeating Characters and Sliding Window Maximum cold. Hide tags, state the invariant first, and add randomized operation histories to Design HashMap.
- MIT 6.042J - asymptotics and invariants Use the asymptotics, state-machine invariants and proof-method readings when a cost or correctness argument is weak. Solve only the matching problems.
- Algorithms lecture notes - amortized analysis and hashing Use note 9 Amortized Analysis for the summation, taxation, charging and potential-function proofs, and note 5 Hashing for chaining, universal hashing and open-addressing analysis, when the handbook treatment is too brief for a proof.
- Algorithmica - memory and data layout Read the memory hierarchy, cache and complexity-model chapters, then measure one contiguous-versus-linked and one hash-versus-ordered workload crossover.
- NeetCode - unseen linear problems Use only for two tag-hidden transfer problems after the AlgoMaster slice. Do not start another full roadmap or watch a solution before the attempt is complete.
- Hypothesis documentation - Quickstart and stateful testing Follow Quickstart for
@givenstrategies and the pytest combination, Configuring test settings formax_examplesandderandomize, then Rule-based state machines (rule,precondition,invariant,run_state_machine_as_test) for randomized operation histories againstdictanddequeoracles. - CPython source - list and dict objects Read
list_resizeinObjects/listobject.cfor the growth formula and pattern comment, and theUSABLE_FRACTIONdefinition, perturbation-probing comment and dummy-entry handling inObjects/dictobject.c. Read the cited functions and comments only.