Two Pointers Pattern
What Is the Two Pointers Pattern?
Two pointers means walking through data with two indices at once, moving each one according to a rule, so that a problem that looks like it needs nested loops (O(n²)) is solved in a single pass (O(n)).
NESTED LOOPS: TWO POINTERS:
for i in 0..n-1: left, right = 0, n-1
for j in i+1..n-1: while left < right:
check(i, j) check(left, right)
move left OR right based on result
~n²/2 pairs checked ≤ n steps — each step rules out
a whole row or column of pairs
The trick is always the same: one comparison tells you that a whole group of candidates can be skipped, so you move a pointer past them.
The Three Shapes
1. OPPOSITE ENDS — pointers start at both ends and move inward
[ L → → → ← ← ← R ]
Uses: pair sums on sorted data, palindromes, reversing,
"container"-style area problems
2. SAME DIRECTION (slow / fast) — both move left to right, fast leads
[ S → → F → → → → ]
Uses: in-place filtering/compaction, removing duplicates,
partitioning, moving zeros
3. TWO SEQUENCES — one pointer in each input
A: [ i → → ] B: [ j → → → ]
Uses: merging sorted lists, intersection, "is A a subsequence of B"
Shape 1: Opposite Ends
Pair With a Target Sum (Sorted Input)
Gift-card balance 14; item prices sorted: [2, 4, 5, 7, 9, 12] Find two items that cost exactly 14. L=0 (2), R=5 (12): 2+12 = 14 ✓ found Another target, 16: L=0 (2), R=5 (12): 14 < 16 → L++ (2 is too small even with the largest) L=1 (4), R=5 (12): 16 = 16 ✓ Why moving L is safe when the sum is too small: nums[L] + nums[R] < target, and nums[R] is the largest remaining value, so nums[L] + (anything else) is even smaller. nums[L] can never be in an answer → discard it.
Palindrome Check, Ignoring Punctuation
"Step on no pets!" L → ← R Skip anything that is not a letter, compare letters case-insensitively, move both inward. Any mismatch → not a palindrome.
Shape 2: Same Direction
Compact Repeated Readings In Place
Sorted sensor readings: [3, 3, 4, 4, 4, 6, 8, 8] Keep one copy of each value, in place, return the new length. slow = 1 (next write position), fast scans from 1: fast=1: 3 == last kept 3 → skip fast=2: 4 new → write at 1 → [3, 4, ...] slow=2 fast=3,4: 4 repeat → skip fast=5: 6 new → write at 2 → [3, 4, 6, ...] slow=3 fast=6: 8 new → write at 3 → [3, 4, 6, 8, ...] slow=4 fast=7: 8 repeat → skip Result: first 4 positions = [3, 4, 6, 8]
Shape 3: Two Sequences
Merge Two Sorted Lists
A = [1, 4, 9] B = [2, 3, 10, 11] Take the smaller front each time: 1(A) 2(B) 3(B) 4(A) 9(A) 10(B) 11(B) → [1, 2, 3, 4, 9, 10, 11] When one list runs out, copy the rest of the other.
Code: All Three Shapes
import java.util.Arrays;
public class TwoPointers {
// Shape 1 — opposite ends on sorted input; returns indices or null
static int[] pairWithSum(int[] sorted, int target) {
int left = 0, right = sorted.length - 1;
while (left < right) {
int sum = sorted[left] + sorted[right];
if (sum == target) return new int[]{left, right};
if (sum < target) left++; // need a bigger sum
else right--; // need a smaller sum
}
return null;
}
// Shape 1 — palindrome check that ignores non-letters and case
static boolean isLetterPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (!Character.isLetter(s.charAt(left))) { left++; continue; }
if (!Character.isLetter(s.charAt(right))) { right--; continue; }
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right)))
return false;
left++; right--;
}
return true;
}
// Shape 2 — keep one copy of each value in a sorted array, in place
static int compactUnique(int[] a) {
if (a.length == 0) return 0;
int slow = 1; // next write position
for (int fast = 1; fast < a.length; fast++)
if (a[fast] != a[slow - 1]) a[slow++] = a[fast];
return slow;
}
// Shape 3 — merge two sorted arrays
static int[] merge(int[] a, int[] b) {
int[] out = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length) out[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];
while (i < a.length) out[k++] = a[i++];
while (j < b.length) out[k++] = b[j++];
return out;
}
public static void main(String[] args) {
int[] prices = {2, 4, 5, 7, 9, 12};
for (int target : new int[]{14, 16, 19, 30}) {
int[] p = pairWithSum(prices, target);
System.out.println("target " + target + ": "
+ (p == null ? "none" : prices[p[0]] + " + " + prices[p[1]]));
}
for (String s : new String[]{"Step on no pets!", "Never odd or even", "Two pointers"})
System.out.println("\"" + s + "\" -> " + isLetterPalindrome(s));
int[] readings = {3, 3, 4, 4, 4, 6, 8, 8};
int len = compactUnique(readings);
System.out.println("compacted: " + Arrays.toString(Arrays.copyOf(readings, len)));
System.out.println("merged: " + Arrays.toString(merge(new int[]{1, 4, 9}, new int[]{2, 3, 10, 11})));
}
}Output:
target 14: 2 + 12
target 16: 4 + 12
target 19: 7 + 12
target 30: none
"Step on no pets!" -> true
"Never odd or even" -> true
"Two pointers" -> false
compacted: [3, 4, 6, 8]
merged: [1, 2, 3, 4, 9, 10, 11]
How to Spot a Two Pointers Problem
STRONG SIGNALS
✓ Input is SORTED (or sorting it doesn't break the question)
✓ "Find a pair / triple with sum / difference ..."
✓ "In place", "O(1) extra space", "without another array"
✓ Compare things from both ends (palindromes, symmetric checks)
✓ Two sorted inputs that must be combined or compared
WEAK SIGNALS — think twice
✗ Input unsorted AND original positions must be returned
→ a hash map is usually simpler (see the Hashing Pattern)
✗ "Contiguous subarray with property X"
→ that's usually Sliding Window (a special case of same-direction pointers)
Extending to Triples
A common next step: three values that sum to a target. Fix one value, then run the opposite-ends pair search on the rest.
sort nums
for i in 0 .. n-3:
if i > 0 and nums[i] == nums[i-1]: continue ← skip repeated anchors
left, right = i + 1, n - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == target: record; move both, skipping repeats
elif s < target: left++
else: right--
Time: O(n log n) sort + O(n²) search = O(n²) (vs O(n³) brute force)
The same "fix k−2 values, two-pointer the last two" idea extends to any k, giving O(n^(k−1)).
Complexity
| Shape | Time | Extra space |
|---|---|---|
| Opposite ends (sorted) | O(n) | O(1) |
| Opposite ends (needs sorting) | O(n log n) | O(1) – O(n) for the sort |
| Same direction | O(n) | O(1) |
| Two sequences (merge) | O(m + n) | O(m + n) for the output |
| Triples (fix one + pair search) | O(n²) | O(1) |
Common Mistakes
Using <= in while (left <= right) for pair search. When left == right you would pair an element with itself. Pairs need left < right.
Applying opposite-ends logic to unsorted data. The move rule ("sum too small → move left") is only valid because of the sorted order.
Forgetting the tails when merging. After the main loop, one input still has elements — copy them.
Losing original indices by sorting. If the problem asks for positions in the original array, either sort pairs of (value, index) or use a hash map instead.
Interview Questions
Q: Prove that the opposite-ends pair search never skips a valid pair.
When the sum is too small, the left value paired with the largest remaining value still falls short, so it cannot pair with anything smaller — discarding it loses nothing. Symmetrically, when the sum is too large, the right value is too big even with the smallest remaining value. Each step removes only a value that cannot be in any answer, so if an answer exists the pointers reach it.
Q: How does same-direction two pointers achieve O(1) space for in-place filtering?
The fast pointer reads each element once; the slow pointer marks the end of the region that already holds the final answer. Writing at the slow pointer never overwrites an unread element because slow never passes fast.
Q: Two pointers vs hash set for pair sum — when would you choose each?
On sorted data, two pointers uses O(1) extra space. On unsorted data where the original indices matter, a hash set or map gives O(n) time without sorting, at the cost of O(n) memory. If the data is unsorted and indices don't matter, sorting plus two pointers is O(n log n) time and O(1) extra space.
Summary
- ›Two pointers turn many O(n²) pair searches into O(n) passes.
- ›Opposite ends — sorted pairs, palindromes, reversing.
- ›Same direction — in-place filtering, compaction, partitioning.
- ›Two sequences — merging and comparing sorted inputs.
- ›The key insight is always: one comparison lets you discard a whole set of candidates.
Next, Sliding Window specialises the same-direction shape for contiguous ranges — the go-to tool for "longest / shortest / count subarrays with property X".
Sorted array, find two values that add to a target. The current pair sum is too small. Which pointer moves?