Day 24 · Closing pincers & the moving spotlight

Two Pointers & Sliding Window

You will be able to

Explain the invariant that lets two pointers on a sorted array discard candidates safely
Apply fast/slow pointers for in-place array work
Build fixed-size window sums that reuse work instead of recomputing
Grow-and-shrink a variable window while maintaining a constraint, with a hash map when needed
Argue why a sliding window is O(n) even though it has two nested-looking loops

Today's ~115 minutes

Spaced-rep warm-up: Day 23 hashing cards + due deck	10 min
ELI5 + tech read, watch the two-pointers visualizer	20 min
Guided: pincers + the spotlight labs	35 min
Practice: two solo with think-aloud protocol	20 min
Project: pattern log section + hand-trace	20 min
Quiz + flashcards	10 min

Builds on: Day 22 — Big O & complexity · Day 23 — Arrays & hashing

The analogy

🧸 ELI5⚙ Tech

Two searchers at opposite ends of a sorted bookshelf want two prices summing to exactly 100. The left one stands at the cheapest book, the right one at the most expensive. Sum too small? Only the LEFT searcher steps inward — a bigger cheap book is the only move that raises the sum. Too big? Right steps inward. Like closing pincers, they meet in the middle having examined each book at most once — no pair-by-pair O(n²) grind, because sortedness lets each comparison eliminate a whole shelf-section of pairs at once.

The moving spotlight: a security guard checks every 30-meter stretch of a fence. The rookie walks to each position and re-inspects all 30 meters — repeating 29 meters of work per step. The veteran slides a spotlight: each step, one new meter enters the beam, one old meter leaves, and she updates her notes for just those two. Same answers, a fraction of the work. That is a sliding window: keep a running summary (a sum, a count-map) of the stretch you're looking at, and update it incrementally as the edges move. Both tricks are the same deep idea — never re-examine what a pointer has already passed.

Why this matters on the job

These two patterns are interview currency — "longest substring without repeating characters" is among the most-asked questions anywhere — but they're also production patterns: rate limiters count events in a sliding time window (Day 45), streaming metrics compute windowed p95 latencies (Day 157), and context-window management for LLM conversations (Day 122) is literally a token budget window sliding over messages. The transferable skill is invariant thinking: stating what stays true at every step and letting that license each pointer move — the same reasoning that powers binary search on Day 33.

Watch it happen

Closing pincers — two-sum on a sorted array, target 10

step 1 / 6

1

3

4

6

8

11

Sorted array, target sum 10. Brute force tries every pair: O(n²). But SORTED order lets two pointers squeeze from the ends.

🎯 Predict modespeed1×

Guided practice

guided 1

Pincers on sorted data

15 min

In pointers_lab.py, implement pair_with_sum(sorted_nums, target) returning the two VALUES (or None). Before coding, write the invariant sentence as a comment — the starter shows the shape.
Test on the provided cases, including no-solution and duplicate-heavy inputs.
Implement is_palindrome_clean(s): pointers from both ends, skipping non-alphanumeric characters, comparing lowercased. ("A man, a plan, a canal: Panama" → True.)
Implement dedupe_sorted_inplace(nums) with fast/slow: return the length of the unique prefix having moved every unique value forward. Verify against sorted(set(nums)).
For each function, add the complexity as a comment: all three are O(n) time; state each one's space.

🐍 python — editable, runs in your browser

# Invariant: if a valid pair exists, both members lie in nums[left..right].
# sum too small -> left += 1 (nums[left] can't pair with anything: right is max)
# sum too big   -> right -= 1 (symmetric)
def pair_with_sum(nums: list[int], target: int) -> tuple[int, int] | None:
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return nums[left], nums[right]
        if s < target:
            left += 1
        else:
            right -= 1
    return None

def dedupe_sorted_inplace(nums: list[int]) -> int:
    if not nums:
        return 0
    slow = 0                            # nums[0..slow] is the clean prefix
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

assert pair_with_sum([1, 3, 4, 6, 8, 11], 10) == (4, 6)
assert pair_with_sum([1, 2, 3], 42) is None
nums = [1, 1, 2, 2, 2, 3]
assert dedupe_sorted_inplace(nums) == 3 and nums[:3] == [1, 2, 3]
print("pincers: all asserts pass")

Ctrl/⌘+Enter runs · Tab indents · numpy/pandas/sklearn auto-load on import (torch and network calls need a local run)

guided 2

The spotlight, fixed then variable

20 min

In window_lab.py, implement max_window_sum(nums, k) the rookie way first (recompute each window: O(n·k)) and the veteran way (slide: O(n)). Time both on 100k elements with k=1000, Day 22 style — feel the difference.
Now the celebrity problem: longest_unique_substring(s) — length of the longest substring without repeating characters. Use the grow/shrink machine from the tech section with a seen-set (or last-index map) as window state.
Trace it by hand on "abcabcbb" in a comment: show left, right, window contents at each step for the first 5 steps. Hand-tracing once is what makes the machine yours.
State the amortized O(n) argument in a comment: how many times can each pointer move, total?

🐍 python — editable, runs in your browser

Ctrl/⌘+Enter runs · Tab indents · numpy/pandas/sklearn auto-load on import (torch and network calls need a local run)

On your own

Two solo, think-aloud protocol

20 min

Solve both using the interview protocol: (a) restate the problem in one sentence; (b) name the pattern and the invariant/window-state; (c) code; (d) state complexity; (e) test edges. Say steps a, b, d OUT LOUD — literally — this is rehearsal for Day 28's timed drill and every interview after.

(1) Best time to buy/sell stock: given prices, max profit from one buy then one sell. (Pattern: one pass tracking min-so-far — a degenerate fast/slow.)

(2) Longest substring with at most k distinct characters: the grow/shrink machine with a frequency map; shrink while the map holds more than k keys.

Hints: for (2), a count hitting zero must DELETE the key from the map, or len(map) lies about distinct count.

Ship before you stop

Pattern log: pincers & spotlights

Add the "Two Pointers & Sliding Window" section to patterns.md, same four-part structure as Day 23: when to reach for each (sorted + pairs → pincers; contiguous-stretch superlatives → window), your five solved problems each with its invariant/window-state written as ONE sentence, recognition cues ("contiguous", "substring", "longest…such that", "sorted array…pair"), and honest costs (needs sortedness or contiguity; the while-inside-for needs the amortized argument stated or interviewers will call it O(n²)). Include your hand-trace of "abcabcbb" — future-you revising on Day 179 will thank present-you. Commit.

Rubric — check what you completed (0/5)

Section added in the four-part structure with all five problems linked to runnable codeEvery solution has its invariant or window-state written as a single sentenceThe amortized O(n) argument for grow/shrink windows is stated correctlyThe timing comparison rookie vs veteran window is recorded with real numbersCommitted with a descriptive message

Common mistakes & misconceptions

Using the sorted two-pointer on unsorted data. The discard argument depends entirely on sortedness; without it the pincers silently skip valid pairs. Sort first (O(n log n)) or use Day 23's hash map.
Calling the grow/shrink window O(n²) because of the nested while. Count total pointer movements: left never retreats, so ≤ 2n body executions — amortized O(n). Say it in interviews.
Recomputing the window summary from scratch each step. The entire speedup is incremental update: add what enters, remove what leaves. If you recompute, you are the rookie guard.
Forgetting to delete map keys whose count reaches zero. len(window_map) then overcounts distinct characters and the shrink condition misfires.
Off-by-one on window length: it is right − left + 1 with inclusive pointers. Hand-trace one example rather than guessing.
Shrinking with if instead of while. One removal may not restore the constraint; shrink until it holds.

Knowledge check

Q1. Sorted two-pointer, sum too small. Why is left += 1 safe — no valid pair missed?

Q2. The grow/shrink window has a for-loop containing a while-loop, yet runs in O(n). Why?

Q3. Which problem statement smells like a sliding window?

Go deeper — curated resources

courseNeetCode Roadmap — Two Pointers & Sliding Window tracks ↗25 min repoTech Interview Handbook — coding-patterns cheatsheets (repo) ↗15 min toolVisuAlgo — array visualizations for tracing ↗10 min

If you have a third hour

Minimum window substring — The boss fight of this pattern (shortest window covering all of t's characters, with counts). Attempt only if today felt smooth — it combines every idea: variable window, frequency maps, and a satisfied-count trick.

Done means

All lab asserts pass; rookie vs veteran timing recorded
Both solo problems solved with the protocol steps spoken aloud
patterns.md section committed with invariants and the amortized argument
Quiz ≥ 2/3

How this connects

← Back: The window's frequency map is Day 23's pattern embedded in a new machine, and the O(n·k) → O(n) win is Day 22's growth-shape thinking applied. Fast/slow dedupe reuses Day 4's in-place mutation understanding.

Forward →: Fast/slow returns with a twist for cycle detection on Day 26. Invariant thinking is the engine of binary search on Day 33. Windowed counting reappears in rate limiters (Day 45), streaming metrics (Day 157), and LLM context budgeting (Day 122).

Unlocks: D26 Linked Lists · D28 Week 4 Checkpoint: Pattern Drill