Opposite-End Pointers

March 2026 · 18 min read

The Core Idea

In the opposite-end pattern, one pointer starts at the beginning of the array and another starts at the end. They move toward each other based on some comparison, and the algorithm terminates when they meet or cross.

This pattern works best when the array is sorted or when the problem involves comparing elements from both extremes. The sorted order creates a monotonic relationship: if the current pair is too small, moving the left pointer right makes it bigger; if too large, moving the right pointer left makes it smaller.

The General Template

int left = 0, right = n - 1;
while (left < right) {
    // Evaluate current pair
    if (condition_met(arr[left], arr[right])) {
        // Record answer
        break; // or continue searching
    } else if (need_larger_value) {
        left++;   // move left pointer right for a bigger element
    } else {
        right--;  // move right pointer left for a smaller element
    }
}

The key question for every problem is: which pointer should move, and why? The answer always comes from the sorted property giving you a guarantee about what moving a pointer does to the result.

Problem 1: Two Sum (Sorted Array)

Problem: Given a sorted array of integers and a target sum, find two numbers that add up to the target. Return their indices.

Example: Array = [2, 7, 11, 15], target = 9. Answer: indices 0 and 1 (values 2 + 7 = 9).

Why Opposite Ends Work

Since the array is sorted, the smallest element is at the left and the largest is at the right. Adding them gives a sum that we can compare to the target:

• If arr[left] + arr[right] == target: we found the pair.
• If arr[left] + arr[right] < target: the sum is too small. We need a bigger left value, so move left right.
• If arr[left] + arr[right] > target: the sum is too large. We need a smaller right value, so move right left.

Step-Through Animation: Two Sum

Array: [1, 3, 5, 8, 12, 15]. Target = 13. Step through to find the pair.

C++ Solution

vector<int> twoSum(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return {left, right};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return {}; // no pair found
}

Problem 2: Container With Most Water

Problem: Given an array of heights, find two lines that together with the x-axis form a container that holds the most water. Return the maximum area.

Example: Heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]. The maximum area is 49 (between heights 8 at index 1 and 7 at index 8, width = 7).

Why Opposite Ends Work

The area between two lines at positions left and right is:

area = min(height[left], height[right]) * (right - left)

Starting from the widest possible container (left=0, right=n-1), we want to try to find taller lines. The crucial insight:

• The shorter line limits the water height.
• Moving the taller line inward can only decrease the width and cannot increase the height (still limited by the shorter one).
• Moving the shorter line inward might find a taller line, potentially increasing the area even though the width decreases.

So we always move the pointer pointing to the shorter line.

Step-Through Animation: Container With Most Water

Heights: [2, 5, 3, 7, 4, 6]. Track the maximum area as pointers converge.

C++ Solution

int maxArea(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int maxWater = 0;
    while (left < right) {
        int w = right - left;
        int h = min(height[left], height[right]);
        maxWater = max(maxWater, w * h);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxWater;
}

Problem 3: Valid Palindrome

Problem: Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring case.

Example: "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not.

Why Opposite Ends Work

A palindrome reads the same forward and backward. We compare characters starting from both ends and work inward. If every matching pair is equal, the string is a palindrome.

• Start left at 0, right at the last index.
• Skip non-alphanumeric characters from both sides.
• Compare the characters (case-insensitive). If they differ, return false.
• If they match, move both pointers inward.
• If the pointers cross without a mismatch, return true.

Step-Through Animation: Valid Palindrome

Checking if "racecar" is a palindrome.

C++ Solution

bool isPalindrome(string s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        while (left < right && !isalnum(s[left]))  left++;
        while (left < right && !isalnum(s[right])) right--;
        if (tolower(s[left]) != tolower(s[right])) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

When to Use Opposite-End Pointers

Look for these signals:

• Sorted array: The problem either provides a sorted array or asks you to sort first.
• Pair search: You need to find two elements satisfying a condition (sum, difference, product).
• Symmetry: The problem involves comparing from both ends (palindromes, mirrored structures).
• Width vs. height tradeoff: Problems where increasing one dimension decreases another (containers, rectangles).

Common Variations

if (sum == target) {
    result.push_back({left, right});
    while (left < right && nums[left] == nums[left + 1]) left++;
    while (left < right && nums[right] == nums[right - 1]) right--;
    left++; right--;
}

Practice Problems

Summary

• Opposite-end pointers start at both extremes and converge toward the center.
• They work because sorted arrays give a monotonic guarantee: moving the left pointer increases values, moving the right decreases them.
• Always move the pointer that can potentially improve the answer.
• Time complexity is O(n) because each pointer moves at most n times and never reverses direction.
• The pattern extends to multi-pointer problems (3Sum, 4Sum) by nesting an outer loop.