Two Pointers: Same Direction and Opposite Direction

Terminology

Term	Definition
Two pointers	A technique using two index variables that traverse the input in a coordinated way, either toward each other (opposite direction) or in the same direction.
Opposite-direction pointers	One pointer starts at the beginning, the other at the end. They move inward until they meet. Used on sorted arrays for pair-sum and container problems.
Same-direction pointers	Both pointers start at the beginning and move forward. One is a "slow" write pointer, the other a "fast" read pointer. Used for in-place removal and partitioning.

Sorted array An array whose elements are in non-decreasing order. Opposite-direction two pointers exploit this ordering to skip impossible pairs. In-place Modifying the input array without allocating a separate output array. Same-direction pointers enable $O(1)$ extra space solutions. Pair sum Finding two elements in a sorted array that add up to a given target. The classic opposite-direction two-pointer problem. Partitioning Rearranging elements so that all elements satisfying a condition come before those that do not. The slow pointer marks the partition boundary. Greedy narrowing The strategy of moving the pointer that is more likely to improve the result. In container problems, move the pointer at the shorter side.

What & Why

Two pointers is one of the most versatile patterns in algorithm design. The idea is simple: instead of nested loops checking all pairs in O(n^2), use two index variables that move through the array in a coordinated way, reducing the problem to O(n).

The technique comes in two main flavors. Opposite-direction pointers start at both ends of a sorted array and walk inward. Because the array is sorted, you can decide which pointer to move based on whether the current sum is too small or too large. Same-direction pointers (also called the "read/write" or "fast/slow" pattern) use one pointer to scan and another to write, enabling in-place transformations like removing duplicates.

Two pointers is the go-to approach when you see: a sorted array, a pair/triplet search, in-place modification, or a problem where brute force uses nested loops over the same array.

How It Works

Opposite Direction: Pair Sum in Sorted Array

Start with left = 0 and right = n - 1. If the sum is too small, move left right (to increase the sum). If too large, move right left (to decrease it).

Same Direction: Remove Duplicates In-Place

Use a slow pointer w (write position) and a fast pointer r (read position). When r finds a new value, copy it to w and advance w.

Complexity Analysis

Problem	Brute Force	Two Pointers	Space
Pair sum (sorted)	$O(n^2)$	$O(n)$	$O(1)$
3Sum	$O(n^3)$	$O(n^2)$	$O(1)$
Remove duplicates	$O(n)$ with extra array	$O(n)$	$O(1)$ in-place
Container with most water	$O(n^2)$	$O(n)$	$O(1)$

Why Opposite-Direction Works

In a sorted array of size $n$, there are $\binom{n}{2} = O(n^2)$ pairs. But the sorted order lets us skip entire groups of pairs. If $A[L] + A[R] < \text{target}$, every pair $(L, R'), R' < R$ is also too small, so we advance $L$. Each step eliminates a row or column of the pair matrix, giving $O(n)$ total steps.

Implementation

Opposite Direction: Two Sum in Sorted Array

ALGORITHM TwoSumSorted(A, n, target)
  INPUT: sorted array A of size n, target sum
  OUTPUT: pair of indices (L, R) such that A[L] + A[R] = target, or NOT_FOUND

  L = 0
  R = n - 1

  WHILE L < R DO
    sum = A[L] + A[R]

    IF sum = target THEN
      RETURN (L, R)
    ELSE IF sum < target THEN
      L = L + 1
    ELSE
      R = R - 1
    END IF
  END WHILE

  RETURN NOT_FOUND
END

Same Direction: Remove Duplicates In-Place

ALGORITHM RemoveDuplicates(A, n)
  INPUT: sorted array A of size n
  OUTPUT: new length with duplicates removed (array modified in-place)

  IF n = 0 THEN RETURN 0

  w = 0

  FOR r = 1 TO n - 1 DO
    IF A[r] != A[w] THEN
      w = w + 1
      A[w] = A[r]
    END IF
  END FOR

  RETURN w + 1
END

Opposite Direction: Container With Most Water

ALGORITHM MaxWaterContainer(heights, n)
  INPUT: array heights of size n
  OUTPUT: maximum area between two lines

  L = 0
  R = n - 1
  best = 0

  WHILE L < R DO
    width = R - L
    h = MIN(heights[L], heights[R])
    best = MAX(best, width * h)

    IF heights[L] < heights[R] THEN
      L = L + 1
    ELSE
      R = R - 1
    END IF
  END WHILE

  RETURN best
END

Real-World Applications

• Database merge joins: when two sorted tables are joined on a key, two pointers walk through both tables simultaneously, matching rows in $O(n + m)$.
• Merge step in merge sort: the classic merge of two sorted halves uses same-direction pointers on both halves.
• Collision detection in physics engines: sweep-and-prune algorithms use sorted coordinate lists with two-pointer scans to find overlapping bounding boxes.
• Audio processing: cross-correlation between two signals uses pointer-based sliding to align waveforms.
• Git diff algorithms: comparing two sorted sequences of line hashes to find insertions and deletions uses a two-pointer walk.

Key Takeaways

• Two pointers reduces $O(n^2)$ pair enumeration to $O(n)$ by exploiting sorted order or partitioning structure
• Opposite-direction pointers work on sorted arrays: move the left pointer to increase the sum, the right pointer to decrease it
• Same-direction pointers enable in-place array transformations with $O(1)$ extra space using a read pointer and a write pointer
• For 3Sum and k-Sum, fix one element and run two pointers on the rest, giving $O(n^{k-1})$ instead of $O(n^k)$
• The "container with most water" problem demonstrates greedy narrowing: always move the pointer at the shorter height