Two pointers

The two-pointer technique uses two indices on a sorted array (or string) to find pairs or partitions in O(n) instead of O(n²).

When to use

• Sorted array — pair with target sum
• Remove duplicates in-place
• Partition array (quickselect preview)

Sorted pair sum

#include 
#include 

int main() {
    std::vector a = {1, 2, 4, 6, 10};
    int target = 10;
    int lo = 0, hi = (int)a.size() - 1;
    while (lo < hi) {
        int s = a[lo] + a[hi];
        if (s == target) {
            std::cout << lo << ", " << hi << "\n";
            break;
        }
        if (s < target) ++lo;
        else --hi;
    }
    return 0;
}

Invariant

If sum too small, advance lo; if too large, shrink hi. Works because sorting orders possibilities.

Important interview questions and answers

1. Q: Why sorted?
   A: Monotonic move of pointers proves we never skip the only valid pair.
2. Q: Two pointers vs hash map?
   A: Sorted + two pointers O(n) time O(1) space; hash map O(n) time O(n) space for unsorted.

Self-check

1. What is time complexity of two-pointer scan?
2. When does moving lo vs hi?

Pitfall: Two pointers on unsorted data for pair-sum usually needs sorting first or a hash map.