Two-Pointer Invariants: Converging, Fast-Slow & Dutch National Flag

Eliminating Rows and Columns in the Pair Search Matrix

Why does the converging two-pointer algorithm for sorted 2-Sum ($A[L] + A[R] = T$) never miss a valid pair? Visualize all possible index pairs $(L, R)$ with $0 \le L < R < N$ as an upper-triangular grid inside an $N \times N$ matrix, starting at the top-right corner $(L = 0, R = N - 1)$:

• If $A[L] + A[R] < T$, since the array is sorted ($A[k] \le A[R]$ for all $k < R$), pairing the current $L$ with any smaller right index $k < R$ yields $A[L] + A[k] \le A[L] + A[R] < T$. Thus the entire row $L$ is provably invalid, and incrementing $L \leftarrow L + 1$ safely discards $R - L$ pairs in $O(1)$ time.
• If $A[L] + A[R] > T$, since $A[k] \ge A[L]$ for all $k > L$, pairing the current $R$ with any larger left index $k > L$ yields $A[k] + A[R] \ge A[L] + A[R] > T$. Thus the entire column $R$ is provably invalid, and decrementing $R \leftarrow R - 1$ safely discards $R - L$ pairs in $O(1)$ time.

The exact same pruning proof governs the Container With Most Water problem ($\max (R - L) \cdot \min(H[L], H[R])$): if $H[L] \le H[R]$, then for every $k \in (L, R)$, the width $(k - L) < (R - L)$ and the height $\min(H[L], H[k]) \le H[L] = \min(H[L], H[R])$. Therefore, $L$ can never form a larger container with any $k < R$, justifying $L \leftarrow L + 1$.

Taxonomy of Multi-Pointer Paradigms

Visualizing Dijkstra's 4-Region Dutch National Flag State

Dutch National Flag State Transitions

Production Implementation: Dijkstra's 3-Way Partition & O(1)-Space Trapping Rain Water

#include <algorithm>
#include <cstdint>
#include <utility>
#include <vector>

// Returns {low, high} bounds of the equal-to-pivot range [low .. high]
template <typename T>
std::pair<std::size_t, std::size_t> dutch_flag_partition(std::vector<T>& a, const T& pivot) noexcept {
  if (a.empty()) return {0, 0};
  std::size_t low = 0;
  std::size_t mid = 0;
  std::size_t high = a.size(); // Use half-open [mid, high) to avoid unsigned underflow!

  while (mid < high) {
    if (a[mid] < pivot) {
      std::swap(a[low], a[mid]);
      ++low;
      ++mid;
    } else if (a[mid] == pivot) {
      ++mid;
    } else {
      --high;
      std::swap(a[mid], a[high]);
      // Critical: do NOT increment mid; the element swapped from a[high] is unclassified!
    }
  }
  return {low, high};
}

// O(N) Time, O(1) Space Converging Two-Pointer Trapping Rain Water
// Invariant: if height[left] <= height[right], then max_left <= max_right (or height[right]
// acts as a guaranteed right-hand wall >= height[left]), so water at left is bounded
// exclusively by max_left.
std::int64_t trap_rain_water(const std::vector<int>& height) noexcept {
  if (height.size() < 3) return 0;
  std::size_t left = 0, right = height.size() - 1;
  int max_left = height[left], max_right = height[right];
  std::int64_t trapped = 0;

  while (left < right) {
    if (max_left <= max_right) {
      ++left;
      max_left = std::max(max_left, height[left]);
      trapped += (max_left - height[left]);
    } else {
      --right;
      max_right = std::max(max_right, height[right]);
      trapped += (max_right - height[right]);
    }
  }
  return trapped;
}