Opposite-Direction Two Pointers

What the pattern actually is

Opposite-direction two pointers is the technique of placing one index at the start of a structure and another at the end, then walking them toward each other based on a comparison, instead of comparing every pair with nested loops. It applies to arrays, strings, and anything else you can random-access — and it almost always requires sorted order or an equivalent monotonic property to be correct.

You should reach for it the moment you see:

• "Given a sorted array..." combined with "find a pair / triplet that sums to X" or "closest to X."
• A palindrome check or any problem comparing a sequence against its own reverse.
• "Rearrange the array in-place" where elements need to be partitioned by a predicate (this shades into the fast/slow "read/write" pointer style — see the comparison table below).
• Merging two already-sorted inputs from their fronts, or a container/area problem where the answer is bounded by the shorter of two sides (the classic "max area" framing).

If the input is not sorted but sorting it wouldn't destroy information you need (e.g., you don't need the original indices), sorting first (O(n log n)) and then applying opposite-direction pointers (O(n)) is a completely standard and expected move — you're trading a hash-map-based O(n) time / O(n) space solution for an O(n log n) time / O(1) space one. Know both and be ready to discuss the trade-off.

Mechanics and template

The canonical skeleton, using the pair-sum-against-a-target framing that every variant of this pattern reduces to:

The invariant that makes this correct: at every step, everything you've walked past on the side you just moved past is provably not part of any better answer, given what you know about the other pointer's current position. That "provably" is the part interviewers want you to say out loud — see the correctness argument below.

Common variations you'll encounter:

Variation	Idea	Example shape
Converge-and-count	Move both pointers inward, counting/recording each valid meeting	pair sum equals target
Converge-and-optimize	Move the pointer that can't possibly improve the answer	container / area problems
Fix one, converge the rest	Outer loop fixes one element, inner two pointers solve the reduced 2-pointer subproblem	k-sum family (3Sum, 4Sum)
Three-way partition	Three pointers (low, mid, high) partition around two boundary values in one pass	Dutch National Flag–style rearrangement
Merge-from-the-ends	Two pointers each anchored at the back of two sorted regions, writing backward	merging into trailing free space

The "fix one, converge the rest" variation deserves a callout: for k-sum problems, you sort once (O(n log n)), then for each fixed choice of the first k-2 elements you run an O(n) two-pointer scan on the remainder. That gives O(n^(k-1)) overall for fixed k — e.g., O(n^2) for 3Sum, which is optimal for that problem given known lower bounds.

Why this is O(n), not O(n^2) — the argument to say out loud

The brute-force version of "find a pair with some property" checks every pair: O(n^2). Two pointers replaces that with a single pass where left only ever increases and right only ever decreases. Each pointer can move at most n times total across the entire algorithm — not per iteration, but for the whole run — because neither one ever backtracks. Since the loop terminates the moment left >= right, and each iteration moves at least one pointer by one step, the loop body runs at most n times. That's the same amortized argument you'll see again in Sliding Window and in Union-Find's path compression: bound the total work across the whole run, not the worst case of a single step.

• Time: O(n) for the core scan (or O(n log n) if you must sort first — the sort dominates).
• Space: O(1) auxiliary — this is the headline advantage over a hash-map approach, which solves the same unsorted pair-sum problem in O(n) time but O(n) space.

Pitfalls and interview gotchas

• Forgetting the sortedness precondition. Two pointers on an unsorted array without first sorting (or without some other monotonic guarantee) is simply wrong — you cannot argue that moving a pointer discards only inferior candidates.
• Duplicate handling in k-sum problems. After sorting, adjacent equal elements will generate duplicate triplets/quadruplets unless you explicitly skip repeats for both the outer fixed index and the inner two pointers. This is the single most common bug in 3Sum-family solutions.
• Off-by-one on pointer crossing. Use left < right (strict) as your loop condition for pair-finding — left <= right will compare an element with itself, which is usually wrong unless the problem explicitly allows it.
• Assuming you can move both pointers on every branch. Some variants only advance one pointer per iteration (converge-and-optimize); collapsing this into "always move both" silently turns a correct O(n) scan into a buggy one that skips valid candidates.
• Losing the original indices after sorting. If the problem wants indices into the original array (not values), sort an array of (value, original_index) pairs, not the raw values.
• Confusing this with Sliding Window. Both use two indices and O(1) space, but opposite-direction pointers converge and only care about the two elements under the pointers; Sliding Window pointers both move forward and track aggregate state (a sum, a frequency map) over everything between them. If you find yourself wanting to know "what's the total of everything between left and right," you've drifted into Sliding Window territory — that's the next topic on this roadmap.

Worked illustration (pattern, not a listed problem)

To internalize the invariant without spoiling a specific interview problem below, here's a generic counting variant: given a sorted array, count how many pairs have a sum strictly less than a target (a building block you'll recognize inside harder problems like counting triplets below a threshold).

Notice the key move: when arr[left] + arr[right] < target, you don't just count one pair — you count right - left pairs in O(1), because sortedness guarantees every element between left and right also satisfies the condition when paired with arr[left]. This "count in bulk instead of one at a time" trick is what separates a senior-level two-pointer solution from a merely correct one.

Opposite-direction vs. the rest of the two-pointer family

Pattern	Pointer movement	Precondition	Typical signal
Opposite-direction (this page)	Converge from both ends	Sorted / monotonic	"sorted array," "pair/triplet sum," "palindrome"
Fast & slow (next page)	Same start, different speeds	Linked structure or functional graph	"cycle," "middle," "duplicate via indices-as-pointers"
Sliding window (next topic)	Both move forward, window grows/shrinks	Contiguous range matters	"longest/shortest subarray/substring satisfying..."
In-place read/write (fast/slow variant)	Both move forward, one lags	In-place compaction	"remove duplicates in place," "move zeroes"

When in doubt, ask: do I only care about the two elements the pointers are on, or do I care about everything between them? The former is this page; the latter is Sliding Window.