Two Pointers

What it is

Two pointers is a family of techniques that tracks two positions in one sequence or across two sequences. Instead of restarting a search for every element, the algorithm moves these positions according to a rule that safely eliminates work.

The pointers usually move monotonically: forward, backward, or toward each other. If each pointer crosses a sequence at most once, the scan takes linear time even when the code contains a loop inside another loop.

The technique is faster than naive enumeration because it uses structure. Sorted values can rule out many candidate pairs at once. Two sorted streams can be merged without repeatedly searching for the next value. A read pointer and a write pointer can transform an array without repeatedly shifting elements.

The essential question is not merely “Where should the pointers start?” It is “Why can this pointer move without losing a valid answer?” A correct movement rule needs an ordering argument, a maintained invariant, or a justified greedy choice.

How to recognize it

Look for these signals:

• The input is sorted, or sorting is allowed without losing necessary information.
• The task involves pairs whose sum, difference, or ordering must satisfy a condition.
• Two sorted sequences must be merged, compared, or matched.
• A sequence must be examined from both ends, especially for symmetry.
• Elements must be filtered, deduplicated, or compacted in place.
• Two boundaries determine which side can be processed next.
• As one candidate position advances, the best compatible position never needs to move backward.

Contiguous ranges can also suggest sliding windows, a closely related specialization. A sliding window maintains information about the entire interval between its pointers; many other two-pointer algorithms care only about the pointed-to elements or the already processed regions.

Before sorting, check whether original order, contiguous positions, or original indices matter. Sorting can destroy the property being tested.

The core technique

1. Opposing pointers: eliminate candidates from both ends

Use this pattern for ordered pair searches and mirrored comparisons. Start one pointer at the left end and the other at the right end.

For a sorted array, consider finding two distinct positions with a target sum:

 def find_pair(a, target):
     left, right = 0, len(a) - 1
     while left < right:
         total = a[left] + a[right]
         if total == target:
             return left, right
         if total < target:
             left += 1
         else:
             right -= 1
     return None

If the sum is too small, every pair using the current left element and a smaller right element is also too small. Discarding that left element is therefore safe. The symmetric argument justifies moving the right pointer when the sum is too large.

For counting rather than finding, the same ordering can eliminate a whole block. When a[left] + a[right] <= limit, all right - left partners between those positions qualify with the left element. Add that count and advance left. Otherwise, decrease right. This counts index pairs, including different positions holding equal values.

A common extension fixes one element and applies this pair count to the remaining suffix. For integer sums, the number of triples in a closed interval [L, U] is the count with sum at most U minus the count with sum at most L - 1. Each triple must have increasing indices so it is counted once.

For mirrored comparisons, advance both pointers while values match. If at most one deletion is permitted, the first mismatch requires checking both possibilities: skip the left element or skip the right element. Each remaining interval must then match without further deletions. Choosing just one skip is not justified.

2. Two-stream scanning: merge or match sorted sequences

Use one pointer per sorted sequence. Compare the current elements and process whichever must come next.

 def merge_sorted(a, b):
     i = j = 0
     out = []
     while i < len(a) and j < len(b):
         if a[i] <= b[j]:
             out.append(a[i])
             i += 1
         else:
             out.append(b[j])
             j += 1
     out.extend(a[i:])
     out.extend(b[j:])
     return out

The invariant is that the output is sorted and contains exactly the consumed elements. Choosing from a on equality preserves a consistent tie order between the streams.

Related scans compute intersections or cancel matching occurrences: on equality, consume one occurrence from each sequence; otherwise, advance the smaller value. Preserve unmatched values when required. Decide whether duplicates represent separate occurrences or should be collapsed.

Greedy matching uses a similar structure. Match the smallest available candidate that satisfies the requirement, but prove that doing so cannot reduce the number of later matches. Sorted inputs alone do not establish greedy correctness.

3. Same-direction pointers: read, write, and join

Use separate read and write positions when constructing a valid prefix in place.

 def deduplicate_sorted(a):
     write = 0
     for read in range(len(a)):
         if write == 0 or a[read] != a[write - 1]:
             a[write] = a[read]
             write += 1
     return write

After every iteration, a[:write] contains the distinct values from the processed input. Because write <= read, writing never overwrites unread data. The returned length identifies the meaningful prefix; the remaining array contents are unspecified.

Another use joins two ordered regions. As candidates in one sorted region increase, advance a pointer in the other until compatibility holds. For example, joining a nondecreasing prefix to a nondecreasing suffix requires the prefix endpoint to be no larger than the suffix start. The suffix pointer never needs to retreat as prefix values increase.

Monotone matching can also work over nonnegative prefix sums. Nonnegativity is important: with negative values, increasing an endpoint need not increase a range sum.

4. Boundary-driven and backward scans

Sometimes pointer movement depends on boundary information rather than the current pair alone. For retained volume between columns, track the maximum height seen from each side. Process the side with the smaller boundary maximum: the opposite boundary is already high enough, so the limiting height there is known. Multiply the depth by the column width when widths vary.

Backward scans are useful when later operations cancel earlier elements. Give each sequence its own pointer and pending-deletion counter. Move backward, increasing the counter at deletion markers and consuming ordinary elements while the counter is positive. Compare only the next surviving elements. Independent counters prevent one sequence's cancellation history from affecting the other.

Common mistakes

• Moving a pointer without proof. State which candidates are discarded and why none can improve the answer.
• Reusing one position twice. Pair scans normally require left < right.
• Confusing index counts with distinct values. Duplicate handling depends on the requested result.
• Ignoring equality rules. Closed intervals and stable merges require deliberate boundary handling.
• Assuming pointer movement is monotone. Negative values or incompatible ordering can break that assumption.
• Overwriting unread input. In-place compaction needs a safe read/write invariant.
• Forgetting exhausted streams or tiny inputs. Empty sequences and single elements often need no scanning.

Complexity

A monotone two-pointer scan is typically O(n) for one sequence or O(n + m) for two sequences: each position is crossed only a constant number of times.

Sorting first usually makes the total O(n log n). Fixing each element and performing a linear pair scan gives O(n²) for triple processing, rather than cubic enumeration.

Pointer state usually takes O(1) auxiliary space. A materialized merge needs O(n + m) output space. Sorting, copied inputs, or stored original indices may require additional memory depending on the implementation.