parikshan

Two Pointers

The core idea

When data has structure (sorted, partitioned, or paired), two indices walking through it can answer questions that look quadratic in linear time. The two pointers are not arbitrary; they encode a monotone invariant that, at each step, tells you which side cannot improve. Move the side that cannot improve. That is the entire pattern.

Three flavours:

  1. Converging (meet-in-the-middle): left starts at 0, right at n-1, they walk toward each other.
  2. Slow / fast: both start at 0; the fast pointer scans, the slow pointer overwrites or lags.
  3. Tandem on two arrays: one pointer per array, advance the one that just contributed.

When to reach for it

Trigger phrases:

  • "sorted array"
  • "pair / triplet that sums to ..."
  • "in-place, O(1) extra space"
  • "remove / move / partition without allocating"
  • "longest palindromic ..." (often expand-around-centre)
  • "the minimum window / largest container that ..."

If a problem feels like sliding window but the input is sorted, you probably want two pointers instead.

How to approach

  1. State the invariant in one sentence. Example: "everything in [0, slow) already satisfies the property".
  2. Decide the initial positions (both ends, or both starts).
  3. At each iteration, ask: which pointer am I sure cannot improve? Move that one.
  4. Always end with a sanity check: the loop terminates because each iteration moves one pointer at least one step.

Real-world applications

  • Streaming merges: merging two sorted streams of events from different services.
  • Compaction: in-place compaction of a buffer that has been logically deleted.
  • Audio / signal processing: aligning two signals by their peaks.
  • Database joins on sorted columns: classic merge join is two pointers.
  • Diff algorithms: aligning two sorted sequences of revisions.

In the AI-integrated workspace

The most common AI mistake on these problems is allocating a new array and writing the result there, when the problem demands in-place edits. The code looks correct, passes the sample, and uses O(n) extra space the spec forbade. Your code review needs the question: "Does this mutate in place?" That single question catches most of the regressions.

The second mistake: an agent that uses two pointers but moves both each iteration unconditionally. That breaks the monotone invariant and produces subtly wrong answers on edge cases (length 1, length 2, all-equal). When you see two pointers, make sure exactly one moves per step except in the small set of problems (like Dutch National Flag) where both can.

Problems in this cluster

Easy: reverse-string, valid-palindrome, merge-sorted-array, remove-duplicates-from-sorted-array, move-zeroes, two-sum-ii-sorted. Medium: three-sum, container-with-most-water, sort-colors, reverse-words-in-string. Hard: trapping-rain-water.

Start with reverse-string. It is two pointers in their purest form.