Two Pointers (Opposite Ends)
Start pointers at both ends of a sorted or symmetric structure and move them toward each other based on a comparison.
Core technique
Put one pointer at each end and discard an endpoint only when you can prove it cannot improve the answer. Sorted order provides that proof for pair sums. Palindrome checks and Container With Most Water use different proofs and do not require sorting.
How to recognize it
- The input is sorted, or sorting it is acceptable because the original indices are not needed.
- You are looking for a pair or triple that reaches a target sum, or gets closest to one.
- You must check or build something symmetric, such as a palindrome, or reverse a sequence in place.
- The answer depends on the two ends, such as the area between two walls in Container With Most Water.
Template
Compare the current pair, then discard the side that cannot improve the answer. For a pair sum on a sorted array, a total that is too small means the left value is too small for every remaining partner, so move left forward. A total that is too large means the right value is too large, so move right back.
Python
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
total = nums[left] + nums[right]
if total == target:
return [left, right]
if total < target:
left += 1
else:
right -= 1
return []Java
int[] twoSumSorted(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left < right) {
long sum = (long) nums[left] + nums[right];
if (sum == target) return new int[] { left, right };
if (sum < target) left++;
else right--;
}
return new int[0];
}JavaScript
function twoSumSorted(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
const total = nums[left] + nums[right];
if (total === target) return [left, right];
if (total < target) left++;
else right--;
}
return [];
}Worked example: Container With Most Water
- This example uses a different movement rule from the pair-sum template: move the shorter wall, without sorting. Use heights 1, 8, 6, 2, 5, 4, 8, 3, 7. Area is the shorter wall times the distance.
- Start with walls at both ends: heights 1 and 7, distance 8, area 8.
- Move the shorter wall. Keeping it can only give equal or smaller areas, because the distance shrinks while the height stays capped by that wall. The 1 moves right to the 8, giving area 7 times 7, which is 49.
- The shorter wall is now the 7 on the right, so it moves inward. The areas along the way are 18, 40, 16, 15, 4 and 6, all below 49.
- The pointers meet and the best area is 49.
Complexity: Container With Most Water takes O(n) time and O(1) extra space with no sorting. The pair-sum template also scans in O(n); if a separate pair-sum problem permits sorting first, include that O(n log n) cost.
Try Container With Most Water on LeetCodeCommon mistakes
- Applying the pair-sum logic to an unsorted array. Without order, a total that is too small tells you nothing about which side to move.
- Using left <= right in a pair problem, which lets one element pair with itself.
- Sorting when the problem asks for indices. Sorting loses the original positions, so keep each index paired with its value first, or use a hash map instead.
- Overflow in Java and similar languages. The sum of two large ints needs a long.
- In 3Sum style problems, forgetting to skip duplicate values for both the fixed element and the moving pointers, which returns repeated triplets.
When this pattern does not fit
- The array is unsorted and you need original indices. A hash map solves it in one pass without sorting.
- You need a contiguous range that satisfies a condition. That is a sliding window.
- Both pointers must move in the same direction, such as removing duplicates in place or partitioning. That is the same-direction variant.