Two Pointers
The two-pointer technique uses two references that move through a data structure, typically an array, to solve problems efficiently. By moving pointers toward each other or in the same direction based on conditions, you avoid nested loops and reduce time complexity from O(n^2) to O(n). This pattern is especially powerful on sorted arrays.
When to Use
- →The array is sorted or you can sort it first
- →You need to find pairs that satisfy a sum or difference condition
- →You need to compare elements from both ends of an array
- →You need to remove duplicates in-place from a sorted array
- →You need to partition an array based on some condition
Approach
The most common variant places one pointer at the beginning and one at the end of a sorted array. Based on the comparison (e.g., whether the sum of the two elements is too large or too small), you move one pointer inward. This guarantees you examine every meaningful pair exactly once.
For problems like 3Sum, you fix one element and apply two pointers on the rest. The key insight is that sorting enables you to skip duplicates and know which direction to move. If the current sum is too small, move the left pointer right to increase it; if too large, move the right pointer left.
The same-direction variant (often called slow/fast pointers) is useful for in-place operations. For example, to remove duplicates from a sorted array, the slow pointer marks the position of the last unique element while the fast pointer scans ahead.
Code Template
// Opposite-direction two pointers (sorted array)
function twoSumSorted(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const sum = nums[left] + nums[right];
if (sum === target) return [left, right];
if (sum < target) left++;
else right--;
}
return [];
}
// Three sum using two pointers
function threeSum(nums) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1, right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++; right--;
} else if (sum < 0) left++;
else right--;
}
}
return result;
}