DSA · Chapter 6 of 40
Two Pointers
The two-pointer technique uses two indices moving through a sequence, usually from both ends toward the middle or both forward at different speeds. It replaces nested loops with a single O(n) pass.
It works best on sorted arrays and on problems about pairs, palindromes, or removing duplicates in place.
Opposite ends
Start left at 0 and right at n-1. Move the pointer that makes the value closer to the target. Used for pair sums and palindrome checks.
Same direction
A slow pointer marks where to write and a fast pointer scans ahead. Used to remove duplicates or zeros in place.
Example 1 (python)
def pair_sum(nums, target):
i, j = 0, len(nums) - 1
while i < j:
s = nums[i] + nums[j]
if s == target:
return (nums[i], nums[j])
if s < target:
i += 1
else:
j -= 1
return None
print(pair_sum([1, 3, 4, 6, 9], 10))Output
(1, 9)Sorted input lets us decide which pointer to move.
Example 2 (python)
def is_palindrome(s):
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
print(is_palindrome('racecar'))Output
TrueComparing from both ends needs no extra memory.
Key points
- Two pointers turn many O(n^2) scans into O(n).
- Opposite-end pointers need sorted data for sum problems.
- Same-direction pointers are used for in-place removal.
- Extra space stays O(1).
💡 Note: If you sort first, remember to add O(n log n) to the total complexity.