DSA · Pattern
Two Pointers
Move two indices through the data to avoid checking every pair. This pattern is especially useful with sorted arrays.
Simple summary: Use one pointer at each end, or a read and
write pointer moving forward. Each pointer usually crosses the input only once.
Example: In sorted
[1, 2, 4, 6, 10] with target sum 8,
start at both ends (1 + 10 = 11, too big) → move the right pointer left → 1 + 6 = 7, too small → move left → 2 + 6 = 8, found.
1. When to use
- Find a pair with a target sum in a sorted array
- Remove duplicates in-place
- Palindrome check (start/end moving inward)
- Container with most water, 3Sum (with sorting)
2. Opposite ends (sorted array)
Example: Sorted [1, 2, 4, 6, 10], target sum 8.
left = 0, right = n - 1
while left < right:
sum = nums[left] + nums[right]
if sum == target: return [left, right]
if sum < target: left += 1 # need bigger sum
else: right -= 1 # need smaller sum
Walkthrough:
left=0, right=4 → 1+10=11 > 8 → right=3
left=0, right=3 → 1+6=7 < 8 → left=1
left=1, right=3 → 2+6=8 → return [1, 3]
Each pointer moves at most n times, so the scan is O(n). If you must sort first, the total becomes O(n log n).
3. Same direction (slow / fast)
Remove duplicates from sorted array in-place:
write = 1
for read in 1..n-1:
if nums[read] != nums[write-1]:
nums[write] = nums[read]
write += 1
return write # new length
read scans every element; write marks where unique values go.
4. Example — Valid palindrome
Ignore non-alphanumeric characters and compare lowercase characters from both ends.
left, right = 0, len(s) - 1
while left < right:
skip non-alnum at left/right
if lower(s[left]) != lower(s[right]): return False
left += 1; right -= 1
return True
5. One more worked example — move zeroes
Move all zeroes to the end while keeping the non-zero values in their original order.
write = 0
for read in 0..n-1:
if nums[read] != 0:
swap(nums[write], nums[read])
write += 1
# [0, 1, 0, 3, 12] becomes [1, 3, 12, 0, 0]
The read pointer finds non-zero values. The write pointer marks the next position to fill. Time is O(n), and extra space is O(1).
6. Two pointers vs hash map
| Two pointers | Hash map |
|---|---|
| Needs sorted order (or sort first) | Works on unsorted |
| O(1) extra space (in-place) | O(n) extra space |
| Great for pairs in sorted data | Great for complement lookup |
Quick revision
- Opposite ends: sorted array, move left/right by comparing sum to target.
- Same direction: read/write for in-place filtering.
- Palindrome: scan inward after skipping characters that do not matter.
- The pointer scan is usually O(n); sorting first makes the total O(n log n).