Two Pointers Technique
The Two Pointers technique uses two index variables that traverse a data structure — usually an array — simultaneously. By moving pointers strategically, we eliminate the need for a nested loop, reducing time complexity from O(N²) to O(N).
Two Pointers problems fall into two categories: opposite direction (pointers start at both ends and move toward each other) and same direction (a slow and a fast pointer both move forward, at different speeds).
1. Opposite Direction Pointers
Place left at index 0 and right at index n-1. Move them toward each other based on a condition. Requires a sorted array in most cases.
Common Pattern:
- Initialize
left = 0,right = n - 1. - Compute a value using both pointers (e.g., sum, area).
- If the value is too small, move
leftright to increase it. - If the value is too large, move
rightleft to decrease it. - Stop when
left >= right.
Problems: Pair Sum, Container With Most Water, Three Sum.
2. Same Direction Pointers (Slow & Fast)
Both pointers start at the beginning and move forward, but at different rates. A slow pointer marks the boundary of the processed region; a fast pointer scans ahead.
Common Pattern:
- Initialize
slow = 0,fast = 1. - Advance
fastthrough the array. - When a valid element is found, advance
slowand write/record the value. - Repeat until
fastreaches the end.
Problems: Remove Duplicates, Move Zeroes, Remove Element.
Why is it O(N)?
Even though we have two pointers, each pointer only ever moves in one direction — never backward. In the worst case, each pointer traverses the entire array once.
Total work = at most 2N steps (left pointer moves at most N times, right pointer moves at most N times), which simplifies to O(N) — a significant improvement over the O(N²) brute-force approach.