Two Pointers

5 questions. Short section, but it contains the first genuinely hard problem in the 150 (Trapping Rain Water) and the first where the correctness proof matters more than the code (Container With Most Water).

The one idea

Two pointers replaces a nested loop by exploiting order — because a single comparison lets you discard a whole range of candidates.

Section 1 removed nested loops by spending memory (hash maps). This section removes them by spending structure: if the input is sorted, or symmetric, or has a monotonic property, one comparison can eliminate many candidates at once.

The characteristic trade against Section 1:

	Hashing (§1)	Two pointers (§2)
Needs	`O(n)` extra memory	Sorted or symmetric input
Gives	`O(n)` on unsorted data	`O(n)` with `O(1)` space
Fails when	Memory is constrained	Input has no exploitable order

Two Sum (§1) and Two Sum II (§2) are the same question with one constraint changed — and that single word "sorted" flips which technique wins. Understanding why is the point of this section.

Why it's `O(n)` even though it looks nested

Both pointers only ever move forward (or toward each other). Neither backtracks. So between them they take at most n steps total, regardless of how the inner loop is written. This is aggregate accounting — bound the total work over the whole run, not the worst case of one iteration.

Easy Valid Palindrome LC 125 13 min Medium Two Sum II — Input Array Is Sorted LC 167 15 min Medium 3Sum LC 15 16 min Medium Container With Most Water LC 11 14 min Hard Trapping Rain Water LC 42 18 min

The four variants you'll meet

A — Converging (opposite ends). lo at the start, hi at the end, walking toward each other. Used when input is sorted or symmetric. Questions 1, 2, 4, 5.

B — Same-direction (slow/fast). Both move forward; slow marks where to write, fast scans. The in-place filter pattern. Appears in Linked List (§6) rather than here.

C — Sort, then fix-and-scan. For k-sum: sort, fix k−2 indices with loops, solve the remaining 2-sum with converging pointers. Question 3.

D — Converging with running state. Carry extra information (a running maximum) alongside the pointers. Question 5.

Prerequisites from Part 1

07 Two Pointers the pattern summary this section instantiates 01 Complexity & Problem Triage the aggregate-accounting argument 04 Ordering §5.1 — sorting arrays, and why Arrays.sort(int[], cmp) doesn't exist

Two pointers vs. sliding window

These get confused constantly. Settle it now, before Section 3:

	Two pointers	Sliding window
What matters	The elements at the pointers	The whole range between them
Movement	Usually toward each other	Both forward, right leads
Needs sorted input?	Usually yes	No
Maintains a summary?	No	Yes (sum, counts, max)
Question shape	"find a pair / triple"	"find the best contiguous run"

The tell: if you care about what's between the pointers, it's a window. If you only care about the two elements you're pointing at, it's two pointers.

How to work this section

Read §1 and §2 only, then attempt cold with a timer (20 min Easy, 35 Medium, 45 Hard).
After the attempt, read §3 and §4 and diff against your own reasoning.
For questions 4 and 5 especially: rehearse the correctness argument aloud. Those two are marked on the proof, not the code.
Use the counter-questions in §3 as a quiz — for each approach, cover the answers and try to defend that solution yourself.
Read §7 last: those are the modified-constraint variants.

What to carry forward

The elimination argument: "if this pair is too small, the left element can't pair with anything still in range, because the right element is the largest remaining."
The exchange argument for greedy pointer movement (Q4) — this is your first encounter with the reasoning that drives all of Greedy (§15).
The dedup skip i > 0 && nums[i] == nums[i-1], which reappears verbatim in Backtracking (§10).
Why sorting is "free" when the dominant term is already O(n²).