The two-pointer technique replaces a nested loop with two indices whose movement is driven by a simple rule. This page covers the three common shapes of the pattern, why discarding elements is safe, worked Python examples for each, and the problems where it does not apply.
The two-pointer technique walks two indices through a sequence — usually one at each end, or both moving forward at different speeds — to solve problems in O(n) that look like they need O(n²). The standard interview tool for sorted-array problems.
| Best | Average | Worst | Space (Worst) |
|---|---|---|---|
Ω(n) |
Θ(n) |
O(n) |
O(1) |
Place pointers at both ends of a sorted array. Compare what they index; based on the comparison, move the left pointer right or the right pointer left, monotonically shrinking the search space. Each pointer moves at most n times — total O(n).
def two_sum_sorted(arr, target):
"""Find two indices in a SORTED array that sum to target. O(n)."""
lo, hi = 0, len(arr) - 1
while lo < hi:
s = arr[lo] + arr[hi]
if s == target:
return (lo, hi)
if s < target:
lo += 1
else:
hi -= 1
return None
def remove_duplicates_in_place(arr):
"""Remove duplicates from a sorted array in place. Returns new length."""
if not arr: return 0
write = 1
for read in range(1, len(arr)):
if arr[read] != arr[read - 1]:
arr[write] = arr[read]
write += 1
return write
print(two_sum_sorted([1, 2, 4, 7, 11, 15], 13)) # (2, 4) — 4 + 11
a = [1, 1, 2, 3, 3, 4]
n = remove_duplicates_in_place(a)
print(a[:n]) # [1, 2, 3, 4]On a sorted array, start one pointer at each end. If the current sum is larger than the target, every pair that uses the right element with any element at or to the right of L is also too large, so the right element can be discarded by moving R left. Symmetrically, a sum that is too small lets you discard the left element. Each step removes one candidate, so the loop runs at most n times. That argument is the whole correctness proof, and it relies entirely on the input being sorted.
In the second shape both pointers move forward. The fast (read) pointer visits every element; the slow (write) pointer marks where the next kept element goes. Everything left of the slow pointer is the answer so far. This gives in-place filtering, deduplication of sorted data, and partitioning in O(n) time and O(1) extra space. Floyd's cycle detection on linked lists is a variant where the fast pointer moves two steps per iteration; if there is a cycle the pointers must meet inside it.
A rough decision rule: if the question asks about pairs or triples in sorted (or sortable) data, use opposite ends. If it asks you to modify an array in place while keeping order, use slow and fast. If it involves a linked list and you cannot index, use pointers moving at different speeds. When the problem talks about a contiguous range whose size changes, it is usually the sliding window pattern, which is a two-pointer special case.
def three_sum(nums):
"""All unique triplets summing to zero. O(n^2)."""
nums.sort()
res = []
for i in range(len(nums) - 2):
if i and nums[i] == nums[i - 1]:
continue # skip duplicate anchors
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s < 0:
lo += 1
elif s > 0:
hi -= 1
else:
res.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo + 1]:
lo += 1
lo, hi = lo + 1, hi - 1
return res
def dedupe_sorted(a):
"""Remove duplicates in place, return new length."""
if not a:
return 0
w = 1
for r in range(1, len(a)):
if a[r] != a[w - 1]:
a[w] = a[r]
w += 1
return w
def is_palindrome(s):
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]:
return False
i, j = i + 1, j - 1
return True
print(three_sum([-1, 0, 1, 2, -1, -4])) # [[-1, -1, 2], [-1, 0, 1]]
print(dedupe_sorted([1, 1, 2, 2, 2, 3, 4])) # 4
print(is_palindrome("racecar")) # True3Sum fixes one element and runs the opposite-end scan on the remainder, which turns an O(n^3) brute force into O(n^2). The duplicate-skipping lines are the part people most often get wrong: without them the output contains repeated triplets.
| Approach | Time | Space | Needs sorted input |
|---|---|---|---|
| Nested loops | O(n^2) | O(1) | No |
| Hash set lookup | O(n) | O(n) | No |
| Sort + two pointers | O(n log n) | O(1) to O(n) | Yes (sorts first) |
For a single pair-sum query on unsorted data, a hash set is usually simpler and faster. Two pointers win when the data is already sorted, when memory is constrained, or when you need all pairs or triples without duplicates.
A useful habit when writing any two-pointer loop is to state the invariant in a comment before writing the body: what is known to be true about everything left of L and right of R, or about everything before the write pointer. If every branch of the loop body either preserves that invariant while moving at least one pointer, or returns, the loop is correct and terminates. Most bugs in interview solutions come from a branch that moves no pointer at all.
lo < hi when an element cannot pair with itself.(value, index) pairs if you need them.