Two Pointers
Quick reference
| Opposite-direction sweep | O(n) |
| Same-direction (slow/fast) sweep | O(n) |
| Brute-force pair check (for comparison) | O(n²) |
Picture two fingers resting on the same array, each free to move independently. The brute-force way to check every pair of elements is a nested loop — for each element, scan every other element again, which is O(n²) work. Two pointers is the realization that for a lot of problems, you don't need every pair — you need the pairs to meet each other in a smart order, so each finger only needs to sweep across the array once.
There are two common ways to place the fingers. One starts them at opposite ends and walks them toward each other, converging in the middle. The other starts them together at the front and lets one race ahead of the other, both moving in the same direction. Which one applies depends on what the problem is actually asking — but both replace an O(n²) nested scan with a single O(n) sweep.
Two pointer shapes
// Opposite-direction: start at both ends, move inward
left = 0
right = length - 1
while left < right:
... look at arr[left] and arr[right] ...
move left forward, or right backward, or both, depending on what you find
// Same-direction: both start at the front; one is the "slow" writer,
// one is the "fast" scanner racing ahead of it
slow = 0
for fast from 0 to length - 1:
... decide whether arr[fast] belongs at position slow ...
if it does: place it there, then slow += 1opposite-direction — converge from both ends
function hasPairWithSum(sortedArr, target):
left = 0
right = length(sortedArr) - 1
while left < right:
sum = sortedArr[left] + sortedArr[right]
if sum == target:
return true
elif sum < target:
left += 1 // sum too small — the only way up is a bigger left value
else:
right -= 1 // sum too big — the only way down is a smaller right value
return falsesame-direction — slow/fast in-place filter
function moveMatchingToFront(arr, matches):
slow = 0
for fast from 0 to length(arr) - 1:
if matches(arr[fast]):
swap(arr[slow], arr[fast])
slow += 1
return slow // everything before this index matches; everything after doesn'tBoth pointer shapes do the same thing to the growth curve: replace a nested O(n²) scan with a single pass where each pointer moves at most n steps total, using nothing but a couple of index variables.
| Operation | Time | Space | Why |
|---|---|---|---|
| Opposite-direction sweep | O(n) | O(1) | left and right together cover at most n total steps before they cross — no element is ever revisited. |
| Same-direction (slow/fast) sweep | O(n) | O(1) | fast visits every element exactly once; slow only ever moves forward, never past fast — combined work is still linear in n. |
| Brute-force pair check (for comparison) | O(n²) | O(1) | Checking every (i, j) pair with a nested loop is the cost two pointers exists to avoid. |
Pointers crossing without a stop condition
Forgetting the crossing check lets left and right sail past each other, or lets fast walk off the end of the array — an infinite loop in the first case, an out-of-bounds read in the second. The loop condition is not optional bookkeeping; it's the thing that guarantees termination.
"Skip duplicates" silently broken
Problems like 3Sum need to skip past repeated values after finding a match, or the same triplet gets reported multiple times. A duplicate-skip written as "skip while arr[i] == arr[i+1]" instead of "skip while arr[i] == arr[i-1]" (or applied to the wrong pointer) either skips too much and misses valid answers, or skips too little and reports duplicates.
Assuming sorted input the pattern actually requires
The opposite-direction pattern above only works because moving left forward strictly increases the sum and moving right backward strictly decreases it — a guarantee that only holds on sorted data. Running it on an unsorted array doesn't crash, it just silently returns wrong answers, because the "too small → move left" logic no longer means what it assumes.
Sign in to mark problems done — progress syncs across devices.