Week 06 — Two Pointers + Sliding Window: Linear-Time Mastery

Month 02 · Week 06 of 24 · 5 flagship problems · Pattern focus: Two Pointers and Sliding Window

Theme: The two patterns that turn quadratic into linear.

Why this week matters

Two pointers and sliding window are the highest-ROI patterns in the interview — they appear in 30–40% of FAANG onsites by themselves or as building blocks. They share the same physical insight: instead of nested loops over (i, j) pairs, advance two indices in lockstep, each at most N times → O(N) total work.

What separates Mid from Senior+ on these problems is recognizing them. The trap is that they look like array problems, so candidates write nested loops and ship O(N²). The signal interviewers look for: do you reach for two pointers / sliding window first?

Specifically:

• Two pointers comes in three shapes — converging (3Sum, Container w/ Most Water), same-direction (slow/fast on linked lists, partition), and meeting (palindrome check).
• Sliding window comes in two shapes — fixed-size (count distinct in window of K) and variable-size (expand-then-contract on a constraint, e.g., longest substring with property P).
• The variable-size variant is where most candidates fail. The discipline: grow the window via right pointer until invariant breaks; shrink via left until invariant restored; record answer at every valid state.

This week’s problems are picked to span the full spectrum: 3Sum (converging two-pointer after sort), Container w/ Most Water (converging two-pointer with a non-obvious move-rule proof), Trapping Rain Water (converging two-pointer + the monotonic-stack alternative — a single problem with three distinct optimal algorithms), Longest Substring Without Repeating (variable-size sliding window, the canonical), Minimum Window Substring (variable-size sliding window, Hard).

Problem set

Daily schedule (suggested)

Readiness gate (before Week 7)

You should be able to:

• Write 3Sum in under 15 minutes with correct dedup (no set of tuples cheat).
• Prove (verbally) why Container With Most Water’s “move shorter pointer” rule is correct.
• Sketch ALL THREE Trapping Rain Water solutions — two-pointer, prefix-max, monotonic stack — and say one sentence on when each is preferable.
• Write Longest Substring Without Repeating in under 10 minutes from scratch using the canonical “char → last-index” map.
• Write Minimum Window Substring in under 25 minutes with the match counter optimization (not naive map equality on every shrink).
• State the two-pointer correctness invariant: “the answer cannot use any pair we’ve eliminated.”
• State the variable sliding-window template: expand right until invariant breaks → shrink left until invariant restored → record answer at every valid state.

If any of these are weak, do not advance. Re-do the failing problem and write the postmortem.

Anti-pattern hit-list (avoid)

• Using a hash set to dedup 3Sum triplets — works, but loses the “sorted-array dedup by skip” signal. Senior+ shows the skip-dedup.
• Moving both pointers simultaneously in Container w/ Most Water — drops the move-rule proof.
• Solving Trapping Rain Water with only ONE approach. The follow-up is always “what’s another way?”
• Variable sliding window where you forget to record the answer inside the while-loop (off-by-one trap).
• Minimum Window Substring with map_a == map_b check on every shrink — that’s O(σ) per shrink → O(Nσ) total. Use a match counter that increments/decrements on each char.

Connections forward

• Week 7 — Prefix sums and binary search (extends the “scan once” mindset to range queries and search-on-monotone).
• Week 8 — Monotonic stacks and intervals (p28 Trapping Rain Water is the bridge problem).
• Phase 02 Lab — lab-01-two-pointers.md, lab-02-sliding-window.md.