Two Pointers

The opposite-direction, same-direction and read/write pointer patterns, and how to prove that moving a pointer never skips the answer.

What you will learn

The opposite-direction, same-direction and read/write pointer patterns, and how to prove that moving a pointer never skips the answer.

Prerequisites: Modules 5 and 18.

Patterns

Opposite-direction pointers, same-direction fast/slow pointers, read/write pointers, merging two sorted sequences, partitioning, and sliding windows.

Problems

Two Sum II, remove duplicates in-place, move zeroes, container with most water, three-sum, four-sum, pair difference, linked-list cycle, and merging sorted arrays.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Two Sum II on a sorted array
    vector<int> a = {1, 3, 4, 6, 8, 11, 15};
    int target = 14, l = 0, r = (int)a.size() - 1;
    while (l < r) {
        int s = a[l] + a[r];
        cout << "l=" << l << " r=" << r << " sum=" << s << (s == target ? "  found" : s < target ? "  too small: l++" : "  too big: r--") << '\n';
        if (s == target) break;
        if (s < target) ++l; else --r;
    }
    // remove duplicates in place (read/write pointers)
    vector<int> d = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
    size_t w = 0;
    for (size_t rd = 0; rd < d.size(); ++rd) if (rd == 0 || d[rd] != d[rd - 1]) d[w++] = d[rd];
    cout << "unique prefix:";
    for (size_t i = 0; i < w; ++i) cout << ' ' << d[i];
    // container with most water
    vector<int> h = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    int i = 0, j = (int)h.size() - 1, best = 0;
    while (i < j) { best = max(best, min(h[i], h[j]) * (j - i)); if (h[i] < h[j]) ++i; else --j; }
    cout << "\nmost water: " << best << '\n';
    // three-sum without duplicate triples
    vector<int> t = {-1, 0, 1, 2, -1, -4};
    sort(t.begin(), t.end());
    cout << "three-sum zero triples:
…

l=0 r=6 sum=16  too big: r--
l=0 r=5 sum=12  too small: l++
l=1 r=5 sum=14  found
unique prefix: 0 1 2 3 4
most water: 49
three-sum zero triples: [-1,-1,2] [-1,0,1]

Correctness

Explain pointer movement invariants and why discarded candidates cannot produce a better answer.

Two Sum II: if a[l] + a[r] < target, then a[l] paired with any index ≤ r is also too small (the array is sorted), so l can be discarded. The symmetric argument discards r.

Container with most water: the area is limited by the shorter line. Moving the taller line inward can only reduce the width without raising the limiting height, so the shorter line is the only one worth moving.

Each step discards one index, so these scans are O(n) after the O(n log n) sort (three-sum is O(n²)).

Quiz

? In Two Sum II, the sum is too small. Why is it safe to discard `l`?
+ Every pair (l, r') with r' ≤ r has an even smaller or equal sum, because the array is sorted. :: No pair using a[l] can reach the target.
- Because l is the smallest index. :: The argument uses sortedness.
- It is a heuristic. :: It is provably safe.
- Because r might be the answer. :: Unrelated.

? In container-with-most-water, why move the pointer at the shorter line?
+ The shorter line limits the area; moving the taller one only shrinks the width without raising that limit. :: The discarded pairs cannot beat the current one.
- To keep the pointers balanced. :: Not the reason.
- It is arbitrary. :: Moving the taller line can miss the optimum.
- Because shorter lines are worth less. :: The proof is about the limiting height.

? Three-sum skips `t[k] == t[k−1]`. What does that prevent?
+ Reporting the same triple twice :: The run printed each triple once.
- Missing a triple :: It does not lose answers.
- Overflow :: Unrelated.
- Sorting errors :: Unrelated.