Two Pointers & Sliding Window

Two pointers and sliding window are two related techniques for problems over arrays and strings. Both exploit the same idea: as a range of the array grows and shrinks, maintain an invariant incrementally instead of recomputing from scratch.

Two Pointers — Opposite Direction

Start one pointer at each end and move them toward each other, using the current state to decide which side to advance. Classic problem: two-sum in a sorted array.

nums = [1, 3, 5, 7, 9, 11],  target = 12

   L →                 ← R
   1  3  5  7  9  11     1 + 11 = 12 ✓

If the sum is too small, the only way to increase it is to move L right; if too large, move R left. Every step eliminates a whole set of impossible pairs, giving O(n).

Two Pointers — Same Direction (Fast & Slow)

Both pointers start at the same end; one runs ahead. This powers linked-list cycle detection (Floyd’s algorithm), removing duplicates in place, and partition-based problems.

nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
         slow fast
      → slow only advances when nums[fast] is new:
         [0, 1, 2, 3, 4] (in place)

Sliding Window — the Generalization

A sliding window is just a range [left, right) with two same-direction pointers. The window invariant must be maintained as right extends and left contracts.

  • Fixed window — length is constant; recompute the metric per slide in O(1). Prime use: rolling-sum/hash problems.
  • Variable window — grow right, then shrink left until the constraint holds again.

Variable window example: longest substring with at most k distinct characters

T = e c e b a ,  k = 2
    L       R
    window [0,3) = "ece"  (2 distinct)  valid
    extend R → "eceb"  (3 distinct)  invalid
    shrink L → "ceb"  (3 distinct)  invalid
    shrink L → "eb"   (2 distinct)  valid, len 2

The invariant is distinct(counter) <= k. We maintain a character-frequency map; adding and removing one character keeps the update O(1), so the whole scan is O(n).

The Unified Pattern

All of these are the same skeleton:

  1. Extend the right end (add one element).
  2. While the window is invalid, shrink the left end (remove elements).
  3. Record the best window seen.

Practice Trajectory

  1. Opposite-direction: two-sum (sorted), container-with-most-water, palindrome pair.
  2. Sliding window fixed: maximum sum of k consecutive elements, substring anagrams.
  3. Sliding window variable: longest substring without repeating characters, minimum window substring, longest substring with at most k distinct chars.
  4. Fast/slow: linked-list cycle, remove duplicates, middle of linked list.

For each problem, write down what the invariant is before coding — the invariant is the entire algorithm.