Two PointersTwo Pointers

Two Pointers (Opposite Ends)

Walk one pointer in from each end of a sorted (or monotone-bounded) array, moving whichever side cannot improve the answer.

Learn Two Pointers (Opposite Ends) →
1
0
↑lo
3
1
4
2
6
3
8
4
11
5
15
6
18
7
21
8
↑hi
1/5Sorted array of 9 values, target 19. Put lo at the smallest and hi at the largest element; the sortedness lets each comparison discard one endpoint.
lo pointerhi pointerEliminatedPair found
PseudocodeLearn Two Pointers (Opposite Ends) →
1lo = 0, hi = n - 1
2while lo < hi:
3  s = a[lo] + a[hi]
4  if s == target: return (lo, hi)
5  if s < target: lo += 1
6  else: hi -= 1
7return not found
Variables
lo0
hi8
target19
Complexity
best O(1)
avg O(n)
worst O(n)
space O(1)
Speed