Contents
- Pattern 1 — Opposite Ends
- Pattern 2 — Same Direction (Slow & Fast)
- When to Use Two Pointers
- Complexity
Start one pointer at the left end (left = 0) and one at the right end (right = n-1).
Move them toward each other based on a condition. Requires the array to be sorted.
Template:
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
// found the answer
} else if (sum < target) {
left++; // need a larger value
} else {
right--; // need a smaller value
}
}
Classic problem — Two Sum on sorted array:
// Input: sorted nums, return indices of two numbers that add to target
public int[] twoSum(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) return new int[]{left + 1, right + 1};
else if (sum < target) left++;
else right--;
}
return new int[]{};
}
Both pointers start at the same end. The fast pointer advances every iteration;
the slow pointer advances only when a condition is met.
This pattern is used for in-place operations like removing duplicates.
Template:
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (/* condition — keep this element */) {
nums[slow] = nums[fast];
slow++;
}
// otherwise skip: fast advances, slow stays
}
// slow is the new length
Classic problem — Remove duplicates from sorted array:
public int removeDuplicates(int[] nums) {
int slow = 0;
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) { // new unique value
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1; // new length
}
- Finding a pair / triplet in a sorted array that satisfies a condition (Two Sum, 3Sum).
- Container / volume problems where both ends are candidates (Container with Most Water).
- Palindrome checks — compare characters from both ends.
- In-place compaction — remove elements, move zeros, dedup (slow/fast pattern).
- Problems where elements are contiguous and the array is sorted.
The opposite-ends pattern usually requires the array to be sorted.
If it isn't, sort it first (adds O(n log n)) or use a HashMap approach.
- Time: O(n) — each pointer moves at most n times, total movement is O(2n) = O(n).
- Space: O(1) — only two index variables, no extra space.