A nightly recon job loads a tenant’s invoice lines, already sorted by amount from the ledger export, and asks: do any two lines sum to this credit memo? The first version nested a scan — for each i, every j > i. Two hundred lines in staging finished in milliseconds. Eighty thousand lines in production were still looping when the job was killed at the fifteen-minute mark.
Nobody picked a bad layout. An array already gives a[i] for free. The job ran the wrong procedure on ordered data: restart the inner scan instead of keeping two indexes that only move.
Two pointers are a one-pass procedure that moves lo/hi (or slow/fast) instead of restarting an inner scan. The names are indexes. The algorithm is the rule that says which one advances, and why that move cannot skip a solution.
This post is the search-and-scan entry after binary search in the Algorithms Roadmap. The hub owns the glossary and catalog. Here we only care about when two indexes replace a nested loop, and when they are just two indexes.
The nested scan that “works”
The credit-memo check looks honest. The amounts are sorted. The nested loop is easy to prove: every unordered pair is visited once.
boolean hasPairSum(int[] amounts, int target) {
for (int i = 0; i < amounts.length; i++) {
for (int j = i + 1; j < amounts.length; j++) {
if (amounts[i] + amounts[j] == target) {
return true;
}
}
}
return false;
}Same shape shows up when someone “merges” two already-sorted arrays by copying both into a third list and nested-searching for the next smallest head. The data was ordered. The inner scan threw that fact away. At fifty lines this is a rounding error. At tens of thousands of lines you paid quadratic time for a question the sorted invariant already made linear.
Note: If the export is already ordered, do not sort again to “make the loop nicer.” If it is not ordered, two pointers that depend on order are not legal yet.
What two pointers actually is
Two indexes, one shared invariant, a move rule.
| Shape | Indexes | Typical job |
|---|---|---|
| Opposite ends | lo at 0, hi at n - 1 | Pair-sum, reverse in place, partition |
| Same direction | slow and fast, both start low | Midpoint, compact-in-place, cycle teaser on a list |
| Two sequences | i on a, j on b | Merge two sorted runs into one |
The procedure is the move, not the fact that you declared two ints. lo++ because the current sum is too small is an algorithm. i++ and j++ in a double for with no invariant is a nested loop with extra names.
Sorted pair-sum from opposite ends
Because the array is sorted, the sum of the current ends tells you which end is wrong.
- Sum too small: the smallest unused value cannot help. Advance
lo. - Sum too large: the largest unused value cannot help. Retreat
hi. - Sum equal: you are done (existence) or you record the pair and keep moving (report-all).
That is the invariant: every discarded end is strictly unable to participate in a remaining solution. You never restart a scan from index 0.
Walk one credit of 20 against five sorted amounts:
amounts: [2, 5, 8, 12, 19] target = 20
lo=0 (2), hi=4 (19) sum=21 > 20 hi--
lo=0 (2), hi=3 (12) sum=14 < 20 lo++
lo=1 (5), hi=3 (12) sum=17 < 20 lo++
lo=2 (8), hi=3 (12) sum=20 == 20 foundFour comparisons. The nested version tries (2,5), (2,8), (2,12), (2,19) before it ever reaches (8,12). Sorted order made those misses predictable; two pointers skipped them without visiting them.
The Java is the walk with a while:
boolean hasPairSum(int[] sorted, int target) {
int lo = 0;
int hi = sorted.length - 1;
while (lo < hi) {
long sum = (long) sorted[lo] + sorted[hi];
if (sum == target) {
return true;
}
if (sum < target) {
lo++;
} else {
hi--;
}
}
return false;
}Casting to long is not decoration. Two int amounts near Integer.MAX_VALUE wrap; a wrapped sum can look “too small” and lo++ will walk off the real pair.
Note: Existence can return on the first hit. If the ticket is “list every unique pair,” stay in the loop and skip duplicate values at both ends so a run of fives does not report (5, 15) twice. That skip is still O(n) — you only move lo and hi forward.
If the data is sorted and the question is a pair of ends — credit memo, two SKUs that fill a bundle price, two timestamps that bracket an SLA — this is the procedure.
Reverse and partition: the same opposite-end walk
You do not need a target sum for lo and hi to be the right tools.
Reverse in place is the trivial payload: swap the ends, step both inward, stop when they meet. No extra array.
void reverse(int[] a) {
int lo = 0;
int hi = a.length - 1;
while (lo < hi) {
int tmp = a[lo];
a[lo] = a[hi];
a[hi] = tmp;
lo++;
hi--;
}
}Partition is the same geometry with a predicate: values that fail a test slide toward hi, values that pass stay toward lo, until the indexes cross. Quicksort’s in-place split is that walk plus a pivot policy — the sort post owns the pivot. The takeaway here is smaller: opposite-end indexes rearrange a block without a second copy when each step only needs the two ends you already hold.
A two-sequence merge is the cousin that does not start at opposite ends. Index i on the first sorted run, j on the second; emit the smaller head and advance that index. Each index only moves forward. That is the honest way to build the third array the recon job used to fill with a double scan.
Fast and slow: two indexes that do not start at the ends
On an array, slow/fast often means “read with fast, write with slow”: compact zeros, drop duplicates in a sorted buffer, copy keepers leftward. fast visits every slot; slow advances only when you keep a value. Extra memory stays O(1) because you overwrite a prefix you no longer need.
On a singly linked list you cannot index the tail in O(1), so opposite-end reverse is a different trick. Fast/slow still works: fast takes two steps, slow takes one. When fast hits the end, slow is at the midpoint — enough to split a list for a merge without a counting pass.
Node midpoint(Node head) {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}The same step sizes are Floyd’s cycle teaser: if fast ever lands on slow after both have moved, the list loops. That is a next-pointer that points backward, not a graph coloring argument. The cycle-detection post in the catalog owns directed and undirected graphs.
Note: Fast/slow on a list assumes you may walk next. If the walk is on a general graph, you are no longer in this post.
When the array is not sorted this is just two indexes
Declare lo and hi on an unsorted amounts[] and keep the pair-sum move rule. lo++ because the sum is “too small” is now a lie. A later larger value that you already skipped at hi might have been the pair. The nested loop was slow and correct. The two-pointer walk is fast and wrong.
Without a sorted invariant, two pointers are just two indexes. Naming them left and right does not create an algorithm.
Fixes that are algorithms:
- Sort first (
Arrays.sort), then run opposite-end pair-sum. You pay the sort; the scan after it is linear. Legal when you can mutate or copy. - Unsorted existence with extra memory: one pass, a
HashSetoftarget - xseen so far. Linear time, linear extra. Different procedure. Use it when you must not reorder.
A two-index copy, a for with i and j = i + 1, a window stored as two ints — none of those become this algorithm because the names match a title. The move has to be justified by order, a write-head, or a step-size invariant.
Complexity
Usual bill for the shapes in this post: O(n) time, O(1) extra. Each index crosses the range at most once. Swaps and writes happen in the existing block.
| Job | Time | Extra space | Hidden cost |
|---|---|---|---|
| Pair-sum on data already sorted | O(n) | O(1) | None if you only need existence |
| Pair-sum after you must sort | O(n log n) | depends on the sort | The sort is the bill; the scan after it is not |
| Reverse / compact / partition in place | O(n) | O(1) | Mutates the array |
| Merge two sorted runs into a third | O(n) | O(n) | The output array, not the indexes |
| Fast/slow midpoint on a list | O(n) | O(1) | Two walks of next, not random access |
O(1) extra means you did not allocate a scratch collection to answer the question. A merge’s output array is the result. A HashSet for unsorted pair-sum is extra — often the right trade, not this procedure.
Distinct from sliding window
Two pointers and a sliding window both use a pair of indexes. They are not the same scan.
Opposite-end two pointers shrink from both ends. lo and hi start at the extremes and move toward each other. The pair you care about is not required to be a contiguous slice — amounts[2] and amounts[7] are a legal pair.
A sliding window grows and shrinks a contiguous range. The right edge advances to include the next element; the left edge advances to drop a prefix that broke a constraint (sum too large, too many unique SKUs, a duplicate in the current span). The answer is always a[left..right], never two distant slots.
If the job is a pair of ends, this post. If the job is a subarray you can point at, the next one.
When not to use
Skip this procedure when:
- The sequence is not sorted and the move rule needs order. Sort first, switch to a set, or keep the nested loop at tiny
n. - The pair must be contiguous. That is a window (or Kadane, or prefix sums), not opposite ends.
- The predicate is not monotonic. If advancing
locan skip a remaining solution, the invariant is gone. Use a real inner scan, or a different procedure. - Opposite ends on a singly linked list. You do not have
a[hi]. Rewire nodes to reverse, or copy to an array if you meant random access. - The JDK already did it.
Collections.reverseon aListshould beat a handwritten walk you will not test at wraparound and duplicates.
JDK: no special type, just indexes
There is no TwoPointers class. The procedure is two ints (or two ListIterators, or two Node references) on storage you already have: T[] or List.
int[] amounts = ledger.sortedAmounts(); // T[] — index is free
List<Integer> boxed = ledger.sortedAmountList(); // List — get(i) is fine on ArrayListOn ArrayList, get(i) is the same random-access story the arrays post told. On a LinkedList, get(i) is a walk — putting lo and hi on that list as indexes silently restores the nested cost. If you needed opposite ends on a linked list, you already wanted a different layout or a node-pointer reverse.
Arrays.binarySearch is not two pointers. It cuts the space in half for a single key. Pair-sum is “do any two add to this.” Binary-searching every complement inside an outer loop is O(n log n) and legal — still not this scan.
Call Arrays.sort / Collections.sort when you must establish the sorted invariant, then run the walk.
Cheat sheet
Job: pair / reverse / partition / compact — not a nested restart
Invariant: sorted (opposite-end sum), or write-head, or step-size
Move: lo++ if too small, hi-- if too large; or slow/fast
Time: O(n) after the data is ordered; O(n log n) if you must sort first
Extra: O(1) for in-place walks; output array for a merge
Not sorted: two indexes, not this algorithm
Not a window: pair of ends vs a contiguous a[left..right]
JDK: int lo, int hi on T[] / ArrayList — no type to importDo:
- Check that the sequence is ordered before you trust
lo++/hi--on a sum. - Cast the sum to
longwhen the addends areint. - Use slow/fast when the job is midpoint, compact, or a list cycle teaser.
- Keep extra memory at
O(1)unless the output itself is a new collection.
Don’t:
- Run opposite-end pair-sum on unsorted data and ship the first green test.
- Name two indexes in a nested
forand log it as two pointers. - Treat a contiguous sliding range as this procedure (or this procedure as a window).
get(i)your way across aLinkedListto fake opposite ends.
Wrap-up
Two pointers replace a restarted inner scan with a move rule. On sorted data, opposite ends answer pair-sum in one pass: too small, advance the left; too large, retreat the right. Reverse and partition reuse that geometry. Fast/slow reuses the idea with a write-head or a double step on a list. Unsorted input does not get the name for free.
The Algorithms Roadmap is the map of which procedure to run on the layout you already have. This one is the linear scan you reach for when the nested loop existed only because nobody kept the second index.