Two pointers (opposite ends)

How does Two pointers (opposite ends) work?

One index sits on the first slot, the other on the last. Together they name a candidate answer.

Read the value at each end and combine them. That gives a sum, a width, or a pair to compare.

Compare the result against the target. The comparison tells you which end is the problem.

If the combination is too small, move the left index right. Sorted order guarantees the value can only rise.

If it is too large, move the right index left. That is the only move that can lower it.

The loop ends when the two indices meet. Every element was read at most once.

Sources: Wikipedia: 3SUM

1. [2, 4, 5, 8, 11] lo=0 hi=4The target is 12. The pointers start at the two ends.
2. 2 + 11 = 13The sum is one over the target. Only the right end can lower it.
3. [2, 4, 5, 8, 11] lo=0 hi=3Now 2 plus 8 is 10, which falls short. Only the left end can raise it.
4. [2, 4, 5, 8, 11] lo=1 hi=3Now 4 plus 8 is 12. The target is hit exactly.
5. answer = [1, 3]Three comparisons over five elements. Nothing was read twice.

function twoPointers(arr, target) {
    let lo = 0;
    let hi = arr.length - 1;
    while (lo < hi) {
        const sum = arr[lo] + arr[hi];
        if (sum === target) return [lo, hi];
        if (sum < target) lo++;
        else hi--;
    }
    return null;
}

function twoPointers(arr: number[], target: number): [number, number] | null {
    let lo = 0;
    let hi = arr.length - 1;
    while (lo < hi) {
        const sum = arr[lo] + arr[hi];
        if (sum === target) return [lo, hi];
        if (sum < target) lo++;
        else hi--;
    }
    return null;
}

def two_pointers(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)
        if s < target:
            lo += 1
        else:
            hi -= 1
    return None

function twoPointers(array $arr, int $target): ?array {
    $lo = 0;
    $hi = count($arr) - 1;
    while ($lo < $hi) {
        $sum = $arr[$lo] + $arr[$hi];
        if ($sum === $target) return [$lo, $hi];
        if ($sum < $target) $lo++;
        else $hi--;
    }
    return null;
}

    public static int[] twoPointers(int[] arr, int target) {
        int lo = 0;
        int hi = arr.length - 1;
        while (lo < hi) {
            int sum = arr[lo] + arr[hi];
            if (sum == target) return new int[] { lo, hi };
            if (sum < target) lo++;
            else hi--;
        }
        return null;
    }

    public static int[] TwoPointers(int[] arr, int target) {
        int lo = 0;
        int hi = arr.Length - 1;
        while (lo < hi) {
            int sum = arr[lo] + arr[hi];
            if (sum == target) return new int[] { lo, hi };
            if (sum < target) lo++;
            else hi--;
        }
        return null;
    }

A worked example of Two pointers (opposite ends)

Container with most water

Each number is the height of a vertical line on a chart. Pick the two lines that hold the most water.

The area is the shorter line multiplied by the distance between them.

Start with the widest possible pair, one line at each end.

Moving the taller line inward can never help, because the shorter one caps the area. So move the shorter line and keep the best area seen.

function maxArea(height) {
    let lo = 0;
    let hi = height.length - 1;
    let best = 0;

    while (lo < hi) {
        const area = Math.min(height[lo], height[hi]) * (hi - lo);
        best = Math.max(best, area);

        // the shorter side caps the area, so it is the only one worth moving
        if (height[lo] < height[hi]) lo++;
        else hi--;
    }

    return best;
}

When should you use Two pointers (opposite ends)?

Use Two pointers (opposite ends) when the problem statement says “sorted array (or you are allowed to sort)”, “find a pair/triple with a target sum” or “squeeze from both ends (container, area)”. A solution built on it usually runs in O(n).

• •sorted array (or you are allowed to sort)
• •find a pair/triple with a target sum
• •squeeze from both ends (container, area)
• •palindrome check

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Two pointers (opposite ends) confused with?

Two pointers (opposite ends) is most often confused with Sliding window (variable), Hash set / map, Two pointers (same direction) and Binary search (array).

• Sliding window (variable): A window keeps a live span and both ends move forward. These pointers start apart and close in.
• Hash set / map: Hashing finds a complement in unsorted data, at the cost of O(n) memory. Two pointers need order but no memory.
• Two pointers (same direction): There both indices move forward, one reading and one writing. Here they approach from opposite ends.
• Binary search (array): Binary search hunts one fixed target and halves the range. Here the pair being compared changes every step.

Common mistakes with Two pointers (opposite ends)

• Forgetting that the input must be sorted

  The whole method rests on order. On unsorted data the comparison points the wrong way.

• Writing lo <= hi

  The condition lo <= hi lets one index pair with itself. A pair of distinct elements needs lo < hi.

• Moving both ends in one step

  A valid pair can then be skipped without ever being tested. Move exactly one end per step.

• Reporting a triple twice

  After a hit, skip the equal values on both sides. Otherwise duplicates come back as separate answers.

Which interview problems use Two pointers (opposite ends)?

Interview problems solved with Two pointers (opposite ends) include Two sum II (sorted input), Three sum, Container with most water, Valid palindrome, Trapping rain water, Sort colors and Squares of a sorted array.

• Two sum II (sorted input): The plain form: move the end that fixes the sum.
• Three sum: Fix one value, then run two pointers over the rest.
• Container with most water: Move the shorter side, because it caps the area.
• Valid palindrome: Compare the two ends, then step inward.
• Trapping rain water: Move the side with the smaller wall and bank the water.
• Sort colors: The two ends collect the zeroes and the twos.
• Squares of a sorted array: The largest square always sits at one of the ends.

What is the time and space complexity of Two pointers (opposite ends)?

The target complexity of Two pointers (opposite ends) is O(n).

n up to 1e6 on sorted input gives O(n) time. Each pointer moves at most n steps, and space is O(1).