Two Pointers
Learn the two pointer technique for solving array problems in O(n) that would otherwise require O(n²).
Two Pointers
The two pointers technique uses two indices moving through an array — either toward each other from both ends, or in the same direction at different speeds. It eliminates the need for nested loops, turning O(n²) solutions into O(n).
Pattern 1 — opposite ends
Two pointers start at opposite ends and move toward each other.
Problem: Given a sorted array, find if any two numbers sum to a target.
def two_sum_sorted(arr, target):
left = 0
right = len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [left, right] # found
elif current_sum < target:
left += 1 # sum too small — move left right
else:
right -= 1 # sum too big — move right left
return [] # not found
arr = [1, 2, 4, 6, 8, 11, 14]
print(two_sum_sorted(arr, 13)) # [2, 4] → 4 + 9... wait → arr[2]=4 + arr[4]=8...
# actually arr[1]=2 + arr[5]=11 = 13 → [1, 5]Why it works on sorted arrays: If the sum is too small, we need a bigger number — move left right. If the sum is too big, we need a smaller number — move right left. The sorted order guarantees we never miss the answer.
Pattern 2 — same direction (fast and slow)
Both pointers start at the same end and move in the same direction at different speeds.
Problem: Remove duplicates from a sorted array in-place.
def remove_duplicates(arr):
if not arr:
return 0
slow = 0 # points to last unique element
for fast in range(1, len(arr)):
if arr[fast] != arr[slow]:
slow += 1
arr[slow] = arr[fast] # place next unique element
return slow + 1 # length of unique portion
arr = [1, 1, 2, 3, 3, 4, 5, 5]
length = remove_duplicates(arr)
print(arr[:length]) # [1, 2, 3, 4, 5]slow tracks the last confirmed unique position. fast scans forward. When fast finds something different from slow, it becomes the next unique element.
Pattern 3 — partition
Partition an array into two groups based on a condition.
Problem: Move all zeros to the end of an array while maintaining order of non-zero elements.
def move_zeros(arr):
slow = 0 # next position for non-zero element
for fast in range(len(arr)):
if arr[fast] != 0:
arr[slow] = arr[fast]
slow += 1
# fill the rest with zeros
while slow < len(arr):
arr[slow] = 0
slow += 1
return arr
arr = [0, 1, 0, 3, 12]
print(move_zeros(arr)) # [1, 3, 12, 0, 0]The three patterns at a glance
Opposite ends: left → ← right
[1, 2, 4, 6, 8, 11, 14]
Same direction: slow →
fast →→→→
[1, 1, 2, 3, 3, 4]
Partition: write →
read →→→→
[0, 1, 0, 3, 12]When to use two pointers
| Signal | Pattern |
|---|---|
| Sorted array, pair with target sum | Opposite ends |
| Remove duplicates in-place | Same direction |
| Palindrome check | Opposite ends |
| Partition around a value | Same direction |
| Linked list cycle detection | Fast and slow |
Two pointers requires a sorted array for the opposite ends pattern. If the array is unsorted, sort it first — still O(n log n) overall, much better than O(n²) brute force.
Complexity
| Pattern | Time | Space |
|---|---|---|
| Opposite ends | O(n) | O(1) |
| Same direction | O(n) | O(1) |
| Partition | O(n) | O(1) |
| Brute force equivalent | O(n²) | O(1) |