Two Pointers

How Two Pointers Works

The core idea is simple: instead of checking every possible pair or subarray with nested loops, maintain two index variables that move strategically based on a condition. There are two main variants:

Opposite-direction pointers (converging): One pointer starts at the beginning and the other at the end. They move toward each other until they meet. This works especially well on sorted arrays.

Pair sum in a sorted array: Given a sorted array and a target sum, place the left pointer at index 0 and the right pointer at the last index. If the sum of the two elements equals the target, you found the pair. If the sum is too small, move the left pointer right to increase it. If the sum is too large, move the right pointer left to decrease it. Each step eliminates an entire row or column of the search space.
Container with most water: Place pointers at both ends. The area is determined by the shorter line times the distance between them. Move the pointer at the shorter line inward, because moving the taller one can never increase the area. This greedy narrowing guarantees you find the maximum.

Same-direction pointers (fast and slow): Both pointers start at the beginning. A "fast" pointer advances on every iteration while a "slow" pointer only advances when a condition is met. This pattern is ideal for in-place modifications.

Removing duplicates from a sorted array: The slow pointer marks the position of the last unique element. The fast pointer scans ahead. When the fast pointer finds a value different from the slow pointer's value, increment the slow pointer and copy the new value there. After one pass, everything up to the slow pointer is the deduplicated result.
Partitioning: Similar to the partition step in quicksort, a slow pointer tracks where the next qualifying element should go, while a fast pointer scans the array for elements that meet the criterion.

Step-by-step example — Pair Sum (target = 16):

Step 1: Array = [1, 3, 5, 7, 8, 9, 11, 15]. Left = 0 (value 1), Right = 7 (value 15). Sum = 16. Match found!
If the target were 12: Sum of 1 + 15 = 16 > 12, so move Right left. Sum of 1 + 11 = 12. Match found.
If the target were 20: Sum of 1 + 15 = 16 < 20, so move Left right. Sum of 3 + 15 = 18 < 20, move Left right. Sum of 5 + 15 = 20. Match found.

Key insight: Two pointers work because each pointer movement provably eliminates candidates that cannot be part of the optimal solution. This requires a monotonic relationship—typically provided by sorting—so that moving one pointer in a direction consistently increases or decreases the quantity of interest.

Interactive Visualization

Watch the two-pointer technique find a pair that sums to the target value in a sorted array. The left pointer advances from the start and the right pointer retreats from the end. When they meet or a match is found, the search is complete.

Set a target sum and click Find Pair to begin.

Speed No steps

Code Implementation

The classic two-pointer pair-sum solution on a sorted array. The left pointer starts at the beginning and the right pointer at the end. Depending on the current sum relative to the target, one pointer moves inward.

def two_pointer_pair_sum(arr, target):
    """Find a pair in sorted array that sums to target.

    Args:
        arr: A sorted list of integers.
        target: The desired pair sum.

    Returns:
        A tuple (i, j) of indices if found, or (-1, -1) if no pair exists.
    """
    left = 0
    right = len(arr) - 1

    while left < right:
        current_sum = arr[left] + arr[right]

        if current_sum == target:
            return (left, right)
        elif current_sum < target:
            left += 1          # Need a larger sum
        else:
            right -= 1         # Need a smaller sum

    return (-1, -1)             # No pair found


def remove_duplicates(arr):
    """Remove duplicates from a sorted array in-place.

    Returns:
        The length of the array after removing duplicates.
    """
    if not arr:
        return 0

    slow = 0
    for fast in range(1, len(arr)):
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]

    return slow + 1


# Example usage
arr = [1, 3, 5, 7, 8, 9, 11, 15]
target = 16
result = two_pointer_pair_sum(arr, target)
print(f"Pair found at indices {result}: "
      f"{arr[result[0]]} + {arr[result[1]]} = {target}")
# Output: Pair found at indices (0, 7): 1 + 15 = 16

public class TwoPointers {

    /**
     * Find a pair in a sorted array that sums to target.
     * Returns an int[] with two indices, or {-1, -1} if not found.
     */
    public static int[] pairSum(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            int sum = arr[left] + arr[right];

            if (sum == target) {
                return new int[]{left, right};
            } else if (sum < target) {
                left++;             // Need a larger sum
            } else {
                right--;            // Need a smaller sum
            }
        }

        return new int[]{-1, -1};   // No pair found
    }

    /**
     * Remove duplicates from a sorted array in-place.
     * Returns the new length.
     */
    public static int removeDuplicates(int[] arr) {
        if (arr.length == 0) return 0;

        int slow = 0;
        for (int fast = 1; fast < arr.length; fast++) {
            if (arr[fast] != arr[slow]) {
                slow++;
                arr[slow] = arr[fast];
            }
        }
        return slow + 1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 8, 9, 11, 15};
        int target = 16;
        int[] result = pairSum(arr, target);
        System.out.printf("Pair found at indices [%d, %d]: %d + %d = %d%n",
            result[0], result[1],
            arr[result[0]], arr[result[1]], target);
        // Output: Pair found at indices [0, 7]: 1 + 15 = 16
    }
}

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

/**
 * Find a pair in a sorted array that sums to target.
 * Returns a pair of indices, or {-1, -1} if not found.
 */
pair<int, int> pairSum(const vector<int>& arr, int target) {
    int left = 0;
    int right = static_cast<int>(arr.size()) - 1;

    while (left < right) {
        int sum = arr[left] + arr[right];

        if (sum == target) {
            return {left, right};
        } else if (sum < target) {
            left++;              // Need a larger sum
        } else {
            right--;             // Need a smaller sum
        }
    }

    return {-1, -1};            // No pair found
}

/**
 * Remove duplicates from a sorted array in-place.
 * Returns the new length.
 */
int removeDuplicates(vector<int>& arr) {
    if (arr.empty()) return 0;

    int slow = 0;
    for (int fast = 1; fast < static_cast<int>(arr.size()); fast++) {
        if (arr[fast] != arr[slow]) {
            slow++;
            arr[slow] = arr[fast];
        }
    }
    return slow + 1;
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 8, 9, 11, 15};
    int target = 16;
    auto [i, j] = pairSum(arr, target);
    cout << "Pair found at indices [" << i << ", " << j
         << "]: " << arr[i] << " + " << arr[j]
         << " = " << target << endl;
    // Output: Pair found at indices [0, 7]: 1 + 15 = 16
    return 0;
}

Complexity Analysis

The two-pointer technique eliminates the need for nested iteration. Each pointer moves at most n times and never backtracks, so the total work is linear. No auxiliary data structures are required beyond the two index variables.

Metric	Complexity	Description
Time	O(n)	Each pointer traverses at most n elements; combined at most 2n steps
Space	O(1)	Only two index variables are used regardless of input size

Note: If the input array is not already sorted, an O(n log n) sorting step is required first. In that case the overall time complexity becomes O(n log n), dominated by the sort. The two-pointer scan itself remains O(n). For problems like "Container With Most Water," the array is not sorted by value but the two-pointer approach still works because the decision to move a pointer is based on height comparisons, not value ordering.

Quiz

Test your understanding of the two-pointer technique with these questions.

Q1. Why does the two-pointer pair-sum technique require the array to be sorted?

Sorting makes the array smaller and faster to traverse

Sorting guarantees that moving the left pointer right increases the sum and moving the right pointer left decreases it

Sorting is not actually required; it works on unsorted arrays too

Sorting allows the use of binary search instead of two pointers

Sorting establishes a monotonic ordering so that moving the left pointer right always increases the element value (and thus the sum), while moving the right pointer left always decreases it. This property lets us confidently discard candidates at each step. Without sorting, we cannot make directional guarantees about the sum.

Q2. Given sorted array [2, 4, 6, 8, 10, 12] and target = 14, what is the first pair of values compared?

4 and 10

6 and 8

2 and 12

2 and 4

The left pointer starts at index 0 (value 2) and the right pointer starts at the last index 5 (value 12). Their sum is 2 + 12 = 14, which equals the target, so the pair is found on the very first comparison.

Q3. In the "remove duplicates from sorted array" problem, what role does the slow pointer play?

It marks the position of the last unique element placed so far

It scans ahead to find the next duplicate

It counts the total number of duplicates

It moves backward to fill gaps left by removed duplicates

The slow pointer tracks where the next unique value should be written. It only advances when the fast pointer discovers a new distinct value, which is then copied to the slow pointer's position. After the scan, elements from index 0 through the slow pointer form the deduplicated array.

Q4. What is the time complexity of the two-pointer pair-sum technique on a sorted array of n elements?

O(n²)

O(n log n)

O(log n)

O(n)

Each step moves exactly one pointer inward, and the two pointers start a total of n positions apart. They can therefore meet in at most n steps, giving O(n) time. This is a significant improvement over the brute-force O(n²) approach of checking all pairs.

Q5. In the "Container With Most Water" problem, why do we move the pointer at the shorter line inward?

Moving the taller pointer would cause an array out-of-bounds error

The area is limited by the shorter line, so keeping it and reducing width can only decrease the area; moving it might find a taller line

The shorter line is always on the left side

It does not matter which pointer we move; the result is the same

The area of water is min(height[left], height[right]) * (right - left). If we move the taller pointer inward, the width decreases and the limiting height stays the same or gets shorter, so the area can only decrease or stay the same. Moving the shorter pointer gives a chance of finding a taller line that could increase the area despite the reduced width.

How Two Pointers Works

Interactive Visualization

Code Implementation

Complexity Analysis

Quiz

Keyboard Shortcuts