Problems
The two pointers technique uses two variables (pointers) that move through an array or string to solve a problem efficiently. Instead of checking every possible pair with nested loops (O(n^2)), two pointers can often solve the same problem in a single pass (O(n)).
The idea is simple: place two pointers at strategic positions, then move them based on some condition until they meet or cross.
Why does it work? Two pointers let you skip comparisons that can't possibly be the answer. By moving one pointer at a time based on a condition, you eliminate large chunks of the search space without checking them.
This only works when the data has some structure you can exploit, most commonly when the array is sorted.
There are two classic setups for two pointers:
1. Opposite ends (converging) One pointer starts at the beginning, the other at the end. They move toward each other. Used when the array is sorted and you need to find pairs.
2. Same direction (fast and slow) Both pointers start at the beginning. One moves faster or under different conditions. Used for removing duplicates, partitioning, or separating elements.
| Approach | Start Position | Movement | Common Use |
|---|---|---|---|
| Opposite ends | left = 0, right = n-1 | Move toward each other | Pair sum, container with water, palindrome |
| Same direction | slow = 0, fast = 0 | Fast moves ahead, slow follows | Remove duplicates, partition, merge |
Start with one pointer at the left edge and one at the right edge of a sorted array. Compare the values at both pointers.
- If the sum is too small, move the left pointer right (increase the sum)
- If the sum is too big, move the right pointer left (decrease the sum)
- If the sum matches, you found your answer
You never need to go back because the array is sorted. Moving left can only increase. Moving right can only decrease. This is what makes it O(n) instead of O(n^2).
Both pointers start at the beginning. The slow pointer tracks where the next valid element should go. The fast pointer scans ahead looking for valid elements.
This is perfect for problems where you need to rearrange elements in-place:
- Remove duplicates from a sorted array
- Move all zeros to the end
- Partition an array around a value
The fast pointer reads, the slow pointer writes. They never go backwards.
Two pointers works when the problem has a monotonic relationship between pointer movement and the answer.
In the sorted pair sum example: moving left increases the sum, moving right decreases it. There's no reason to go back because the relationship is predictable.
If the array is not sorted and there's no clear direction to move, two pointers might not apply. In those cases, consider sorting first or using a hash map instead.
| Brute Force | Two Pointers | |
|---|---|---|
| Time | O(n^2) - check all pairs | O(n) - single pass |
| Space | O(1) | O(1) |
| Requirement | None | Usually needs sorted input |
Two pointers trades a sorting requirement for a massive speed improvement.
Look for these clues:
- The array is sorted (or you can sort it)
- You need to find a pair or subarray with a certain property
- The problem asks to do something in-place (no extra array)
- You see words like "two elements", "pair", "partition", "rearrange"
- A brute force approach would use two nested loops
1. Forgetting the array must be sorted. Opposite-end two pointers only works on sorted arrays. If the input isn't sorted, sort it first or use a different technique.
2. Using <= instead of < in the while condition.
while left < right is correct. while left <= right makes the pointers overlap and you might use the same element twice.
3. Not moving the pointer after finding a match. If you need all pairs (not just one), remember to move both pointers after finding a match. Otherwise you'll loop forever.
4. Confusing with sliding window. Two pointers and sliding window are related but different. Two pointers typically converge from opposite ends. Sliding window uses two pointers moving in the same direction to track a range.
| Technique | Pointer Setup | Best For |
|---|---|---|
| Two Pointers (opposite) | left=0, right=n-1, converge | Pair sum, container with water, palindrome check |
| Two Pointers (same dir) | slow=0, fast=0, both move right | Remove duplicates, partition, merge |
| Sliding Window | left=0, right=0, expand/shrink | Subarray with sum, longest substring, min window |
| Fast and Slow | Both start at head, one moves 2x | Cycle detection, find middle of linked list |