Two Pointers (Pair Sum)

Intuition

Suppose you have a gift card worth exactly 1,000 rupees and a shelf of items arranged from cheapest to most expensive. You want two items that use the card exactly. A sensible shopper grabs the cheapest item with one hand and the most expensive with the other. If the total is too high, the expensive item is the problem, so you put it back and pick the next one down. If the total is too low, the cheap item is holding you back, so you swap it for the next one up. Your hands walk toward each other and you never reconsider a combination you have already ruled out.

That is the entire technique. Sorting is what gives each move meaning: moving the left pointer right can only increase the sum, and moving the right pointer left can only decrease it. With that monotonic control, one comparison per step tells you exactly which pointer to move.

How it works step by step

1. Make sure the array is sorted in ascending order (sort it first if it is not, and remember that sorting loses original indices).
2. Set left = 0 and right = n - 1.
3. While left < right, compute sum = nums[left] + nums[right].
4. If sum == target, return the pair.
5. If sum < target, increment left to bring in a larger number.
6. If sum > target, decrement right to bring in a smaller number.
7. If the pointers meet without a match, no valid pair exists.

Why it never skips the answer: when sum > target, the value at right is too big even when paired with the smallest remaining candidate nums[left], so it is too big with every remaining partner and can be discarded forever. The symmetric argument holds for left when the sum is too small. Every move eliminates one element safely, so after at most n - 1 moves the search is complete.

Dry run

Sorted array [1, 3, 4, 6, 8, 11], target 10.

Five steps instead of the 15 pairs a brute-force double loop would check. On an array of 100,000 elements, the gap becomes 100,000 steps versus about five billion.

Code

import java.util.Arrays;

public class PairSum {
    /** Returns indices {i, j} with i < j and nums[i] + nums[j] == target, or null. */
    public static int[] pairSum(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            long sum = (long) nums[left] + nums[right]; // no int overflow
            if (sum == target) return new int[] {left, right};
            if (sum < target) left++;
            else right--;
        }
        return null;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 4, 6, 8, 11};
        System.out.println(Arrays.toString(pairSum(nums, 10))); // [2, 3]
        System.out.println(Arrays.toString(pairSum(nums, 100))); // null
    }
}

def pair_sum(nums, target):
    """nums must be sorted ascending. Returns (i, j) or None."""
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return left, right
        if s < target:
            left += 1
        else:
            right -= 1
    return None


print(pair_sum([1, 3, 4, 6, 8, 11], 10))   # (2, 3)
print(pair_sum([1, 3, 4, 6, 8, 11], 100))  # None

Time and space complexity

Each iteration moves exactly one pointer one position inward, and the pointers start n - 1 apart, so the loop runs at most n - 1 times. Only two integer indices are stored. If the input arrives unsorted, the sort dominates; in that case a hash map solution is O(n) time but costs O(n) space.

Edge cases

• Fewer than two elements: left < right is false immediately, return no pair.
• No valid pair: the pointers meet; return null, None, or an empty array as the problem specifies.
• Using the same element twice: left < right (not <=) prevents pairing an element with itself.
• Duplicates such as [2, 2, 3] with target 4: works, because the two 2s sit at different indices.
• Negative numbers and zero: the logic depends only on ordering, so negatives are fine.
• Large values: in Java, two ints near the limit can overflow when added; widen to long.

Common mistakes

• Applying it to unsorted data. The pointer moves are only justified by sorted order. On unsorted input it misses valid pairs without any error.
• Sorting and then returning the new indices when the problem asks for original positions. Sort pairs of (value, original index) or use a hash map instead.
• Writing `while (left <= right)`. That lets a single element pair with itself.
• Moving both pointers after a match when the task is to count all pairs, without handling duplicates. With repeated values you must skip over equal runs or count combinations explicitly.
• Moving the wrong pointer. If the sum is too small, the *left* pointer moves; mixing this up is the most common whiteboard slip.

Variations and when to use it

Opposite-direction pointers (this lesson) solve pair sum, 3Sum (fix one element, run pair sum on the rest), 3Sum closest, container with most water, and palindrome checks. Same-direction pointers, also called fast and slow or read and write pointers, compact arrays in place: moving zeroes, removing duplicates, merging sorted arrays. When the same-direction pointers define a contiguous range whose contents you track, the pattern becomes a sliding window.

Reach for opposite-direction pointers when the input is sorted (or can be sorted cheaply) and the question involves a pair whose combined value is monotonic as you move inward. If the data cannot be sorted or original indices must be preserved, a hash map gives O(n) time instead. If you only need to look up one partner for each element, binary search gives O(n log n), but two pointers is strictly better here.

Related LeetCode problems

• #167 Two Sum II - Input Array Is Sorted — exactly this algorithm, with 1-indexed output.
• #1 Two Sum — unsorted with original indices required, so a hash map beats sorting plus two pointers.
• #15 3Sum — sort, fix each element, and run pair sum for its negation while skipping duplicates.
• #16 3Sum Closest — same loop, tracking the sum with the smallest distance to target.
• #11 Container With Most Water — start at both ends and always move the shorter wall inward.
• #1679 Max Number of K-Sum Pairs — sort, then on each match count a pair and move both pointers.
• #283 Move Zeroes — the same-direction cousin: a write pointer trails a read pointer.
• #392 Is Subsequence — one pointer per string, advancing the subsequence pointer only on a match.

FAQ