Solve O(n²) problems in O(n) — the two-pointer technique and when to apply it.
Published March 10, 2025
The two-pointer technique uses two indices that move through an array (or string) to avoid nested loops — turning O(n²) into O(n).
// Check if a sorted array has a pair summing to target
public boolean hasPairSum(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) return true;
if (sum < target) left++; // need larger sum → move left pointer right
else right--; // need smaller sum → move right pointer left
}
return false;
}
// Remove duplicates from sorted array in-place
public int removeDuplicates(int[] nums) {
int slow = 0;
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}
| Problem | Strategy |
|---|---|
| Two Sum (sorted array) | Opposite ends |
| 3Sum | Fix first, opposite ends for rest |
| Container With Most Water | Opposite ends, move shorter side |
| Valid Palindrome | Opposite ends |
| Remove Duplicates | Slow/fast same direction |
| Merge Sorted Arrays | Two arrays, two pointers |
When you see a sorted array + pair/triplet problem, immediately think two pointers. The key insight: in a sorted array, moving left right increases the sum; moving right left decreases it. This guarantees you find the answer without missing any pair.