Two pointers is the highest-leverage pattern in array problems: it repeatedly converts O(n²) nested loops into a single O(n) pass. But it only works under specific conditions, and recognizing which sub-pattern applies is the actual skill.
The Core Idea
Instead of two independent indices exploring every pair, two indices move with intent, and at each step you eliminate a class of candidates:
i → ← j
[a, b, c, d, e, f, g]
The key question for every problem: "Can I decide, by moving one pointer, that an entire set of pairs is impossible?" If yes — two pointers applies.
Sub-Pattern 1: Opposite Directions (Sorted Array)
Unlock condition: the array is sorted (or can be sorted), and you're looking for a pair/triple matching a target.
vector<int> twoSum(vector<int>& nums, int target) {
int i = 0, j = nums.size() - 1;
while (i < j) {
int sum = nums[i] + nums[j];
if (sum == target) return {i, j};
else if (sum < target) i++;
else j--;
}
return {};
}
Why it's correct: when sum < target, nums[i] + nums[j'] for any j' < j is even smaller — so the whole row of pairs with index i is eliminated in one move. That elimination is what gives O(n).
Sub-Pattern 2: Same Direction (The Fast and the Slow)
Unlock condition: you need to process a sequence with a window of invariants — duplicates, grouping, in-place moves.
int removeDuplicates(vector<int>& nums) {
int write = 0;
for (int read = 0; read < nums.size(); read++) {
if (nums[read] != nums[write]) {
nums[++write] = nums[read];
}
}
return write + 1;
}
write and read move in the same direction; write lags, compacting the array. Same shape powers "move zeros to the end", "remove element", and the interview favorite 3Sum:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
for (int a = 0; a < (int)nums.size() - 2; a++) {
if (a > 0 && nums[a] == nums[a-1]) continue;
int i = a + 1, j = nums.size() - 1;
while (i < j) {
int s = nums[a] + nums[i] + nums[j];
if (s == 0) {
res.push_back({nums[a], nums[i], nums[j]});
while (i < j && nums[i] == nums[i+1]) i++;
while (i < j && nums[j] == nums[j-1]) j--;
i++; j--;
} else if (s < 0) i++;
else j--;
}
}
return res;
}
Sub-Pattern 3: The Sliding Window (Two Same-Direction Pointers)
Unlock condition: you need a contiguous subarray/substring satisfying a condition, and the condition monotone — shrinking the window never creates a violation you didn't have.
function lengthOfLongestSubstring(s) {
const last = new Map();
let left = 0, best = 0;
for (let right = 0; right < s.length; right++) {
if (last.has(s[right]) && last.get(s[right]) >= left) {
left = last.get(s[right]) + 1;
}
last.set(s[right], right);
best = Math.max(best, right - left + 1);
}
return best;
}
The invariant: window [left, right] always has unique characters. right grows; left jumps forward only when forced.
When Two Pointers Does NOT Apply
| Temptation | Why it fails | What to use |
|---|
| Unsorted array, pair sum | No elimination order | Hash map, O(n) |
| Subarray with product/sum condition (non-monotone) | Shrink doesn't preserve invariant | Hash map / prefix sums |
| Finding any k elements | Window logic can't express "any" | Selection algorithm / heap |
Recognition Drill
When you see a problem, ask in this order:
- Sorted? Or sortable? → opposite-direction pointers for pairs
- In-place compaction / grouping? → same-direction fast/slow
- Contiguous window with monotone condition? → sliding window
- None of the above → hash map or prefix sums, probably
Complexity Cheat Sheet
Pair sum (sorted): O(n) vs O(n²) brute force
3Sum: O(n²) vs O(n³) brute force
Longest unique substring: O(n) vs O(n²)
In-place dedup: O(n) vs O(n) but with extra space
The pattern is not "use two variables." It is structured elimination: every pointer move discards candidates you can prove are useless. Practice it on the sorted-pair problems until the elimination argument is reflexive — that's when 3Sum and the window problems start feeling like the same problem.
Discussion (1)
Sign in or create an account to join the discussion.
2mo ago
The 3Sum walkthrough is the clearest I have read on this. The in-place swap diagram really helps.