Two-Pointer Technique

Also Known As

TL;DR

Explanation

Two pointers typically start at opposite ends of a sorted array (or one at start, one ahead). By moving them based on comparison results, problems that would require nested loops become linear. Classic uses: finding a pair that sums to a target, removing duplicates from a sorted array, merging two sorted arrays. The fast/slow pointer variant (Floyd's algorithm) detects cycles in linked lists.

Diagram

flowchart TD
    ARR[Sorted array: 1 2 4 6 8 10<br/>Find pair summing to 10]
    subgraph TwoPointer
        L[Left pointer at 1]
        R[Right pointer at 10]
        CHECK{Sum = 11 > 10}
        CHECK -->|too big - move right left| R2[Right moves to 8<br/>1+8 = 9 < 10]
        R2 -->|too small - move left right| L2[Left moves to 2<br/>2+8 = 10 found!]
    end
    subgraph Complexity
        NAIVE[Naive O of n squared<br/>check all pairs]
        TP[Two pointer O of n<br/>one pass]
    end
style L fill:#1f6feb,color:#fff
style R fill:#d29922,color:#fff
style L2 fill:#238636,color:#fff
style NAIVE fill:#f85149,color:#fff
style TP fill:#238636,color:#fff

Common Misconception

Why It Matters

Common Mistakes

• Not sorting the array first when the algorithm requires sorted input.
• Moving both pointers by one each iteration — the correct move depends on which pointer's value is larger.
• Off-by-one errors in the loop termination condition — use strict less-than for opposite-end pointers.
• Forgetting that this technique requires sorted data for sum/target problems.

Code Examples

// O(n²) — nested loop to find pair summing to target:
function hasPairWithSum(array $arr, int $target): bool {
    for ($i = 0; $i < count($arr); $i++)
        for ($j = $i + 1; $j < count($arr); $j++)
            if ($arr[$i] + $arr[$j] === $target) return true;
    return false;
}

// O(n log n) sort + O(n) two-pointer = O(n log n) total:
function hasPairWithSum(array $arr, int $target): bool {
    sort($arr);
    $left = 0; $right = count($arr) - 1;
    while ($left < $right) {
        $sum = $arr[$left] + $arr[$right];
        if ($sum === $target) return true;
        $sum < $target ? $left++ : $right--;
    }
    return false;
}

References

• ↗ https://en.wikipedia.org/wiki/Two-pointer_technique

Tags

Related Terms