leetExpert

Module 10 · Two Pointers

Practice

Practice~2 min

How to practice this module

Two-pointers drills reward proving the walk is safe: each move eliminates a candidate region. Start with converging pointers on sorted input (Two Sum II, Container, 3Sum), then the Dutch national flag, then Trapping Rain Water which combines the invariant with running maxima. Done when all five show Solved in the hub.

Problems

Two Pointers — work them in order; difficulty ascends.

0/5

solved

  1. 1Two Sum II (Sorted Input)MediumConverging pointersWatch for: Move the pointer that overshoots — too big shrinks the right, too small grows the left
  2. 2Sort Colors (Dutch National Flag)MediumThree-way partitionWatch for: Swap a 0 to the front and a 2 to the back; only the value 1 advances the middle pointer
  3. 3Container With Most WaterMediumConverging areaWatch for: Move the shorter side — the area is bounded by the shorter height, so moving the taller side can never win
  4. 43SumMediumSort + two-pointer per pivotWatch for: Skip duplicate pivots and duplicate pairs; the search target is the complement, not a fixed pair
  5. 5Trapping Rain WaterHardTwo-pointer running maximaWatch for: Water at a column is bounded by min(maxLeft, maxRight) — advance the side with the smaller running max

Cheatsheet

Two Pointers — Opposite ends or same direction — drop a nested loop.

Smell → pattern

  • Sorted array, pair / triplet sumOpposite ends
  • Remove / move while reading aheadFast / slow
  • Container / area between indicesInward from tallest hope
  • Merge two sorted streamsOne pointer each

Patterns

Opposite ends

Core

Smell: Sorted + target sum

Start L=0, R=n−1. Move the end that makes the sum closer to the target. Sorting (if allowed) is the enabling step.

LR

Fast & slow (same array)

Safe

Smell: Read ahead, write behind

Slow marks the boundary of the kept region; fast explores. Same skeleton as array write-pointer drills.

write region

Inward area search

Reach

Smell: Width × min height style scores

Width shrinks as pointers meet — only move the shorter side, because moving the taller one cannot improve the min.

LR

Two-list merge walk

Core

Smell: Combine sorted inputs

Always take the smaller head. When one list exhausts, append the rest. Linear in combined length.

headrewire

Complexity targets

  • Opposite ends on sorted

    Time
    O(n)
    Space
    O(1)
    Note
    Plus sort if needed

  • Fast / slow rewrite

    Time
    O(n)
    Space
    O(1)
    Note
    In-place

  • Merge two sorted

    Time
    O(n+m)
    Space
    O(1)*
    Note
    *or O(n+m) for a new array

Traps

  • Forgetting the sort prerequisite

    Opposite-end sum logic is wrong on unsorted data. Either sort first (and handle index requirements) or pick another pattern.

  • Crossing pointers

    Loop condition is usually L < R. Equality can double-count the middle element — know whether the problem allows it.