Two-Pointer Techniques

Two-pointer techniques maintain two indices (left and right, or read and write) that traverse a slice or pair of slices in coordinated steps, solving pair-sum, partitioning, in-place compaction, and sorted-merge problems in $O(n)$ time and $O(1)$ auxiliary memory.

1. Converging Opposite-End Pointers (`left = 0`, `right = n - 1` on a Sorted Slice):
   `left` ---> [ 2 | 5 | 8 | 12 | 19 | 25 ] <--- `right`
   - If `arr[left] + arr[right] < target`: `left += 1` (need larger sum)
   - If `arr[left] + arr[right] > target`: `right -= 1` (need smaller sum)

2. Same-Direction Read/Write Pointers (In-Place Compaction / Partition):
   [ 2 | 4 | 6 | 3 | 7 | 8 ]
             ^       ^
          `write`  `read`

Avoiding Unsigned Underflow (0usize - 1) in Converging Two-Pointers

In Rust, slice indices have type usize. In a converging two-pointer loop where right starts at slice.len() - 1 and decrements (right -= 1), you must check slice.is_empty() upfront (or guard while left < right), because computing 0usize - 1 on an empty slice panics with integer underflow in debug mode (and wraps to usize::MAX in release mode)!

Even cleaner: when a converging two-pointer scan only inspects the outer elements and shrinks inward from either end, you can re-slice the borrowed slice (let mut s = slice;) using pattern matching while let [first, .., last] = s—which is 100% immune to index underflow and eliminates all bounds checks!

use std::cmp::Ordering;

/// 1. Idiomatic slice-pattern converging two-pointer search on a sorted slice!
///    Impossible to underflow `0usize - 1` on empty slices and has zero bounds checks!
pub fn sorted_two_sum(sorted: &[i64], target: i64) -> Option<(i64, i64)> {
    let mut window = sorted;
    while let [first, .., last] = window {
        match (*first + *last).cmp(&target) {
            Ordering::Equal => return Some((*first, *last)),
            Ordering::Less => window = &window[1..],                  // Advance left
            Ordering::Greater => window = &window[..window.len() - 1], // Shrink right
        }
    }
    None
}

/// 2. Container With Most Water / Trapping Bounds using indexed `left < right`:
pub fn max_area_container(heights: &[u64]) -> u64 {
    if heights.len() < 2 {
        return 0;
    }
    let mut left = 0usize;
    let mut right = heights.len() - 1;
    let mut max_area = 0u64;

    while left < right {
        let width = (right - left) as u64;
        let h = heights[left].min(heights[right]);
        max_area = max_area.max(width * h);

        // Always advance the shorter wall inward:
        if heights[left] <= heights[right] {
            left += 1;
        } else {
            right -= 1;
        }
    }
    max_area
}

/// 3. Dutch National Flag (3-Way Partition: `< pivot`, `== pivot`, `> pivot`) in O(n) time, O(1) space:
pub fn sort_three_colors(arr: &mut [u8]) {
    let mut low = 0usize;
    let mut mid = 0usize;
    let mut high = arr.len(); // Exclusive upper bound avoids `0 - 1` underflow on empty slice!

    while mid < high {
        match arr[mid] {
            0 => {
                arr.swap(low, mid);
                low += 1;
                mid += 1;
            }
            1 => {
                mid += 1;
            }
            _ => {
                high -= 1;
                arr.swap(mid, high);
            }
        }
    }
}

fn main() {
    assert_eq!(sorted_two_sum(&[], 10), None); // Empty slice handled safely!
    assert_eq!(sorted_two_sum(&[2, 7, 11, 15], 18), Some((7, 11)));

    let heights = [1, 8, 6, 2, 5, 4, 8, 3, 7];
    assert_eq!(max_area_container(&heights), 49);

    let mut colors = [2, 0, 2, 1, 1, 0];
    sort_three_colors(&mut colors);
    assert_eq!(colors, [0, 0, 1, 1, 2, 2]);

    println!(
        "Two-sum: {:?}, Max container: {}, 3-way partition: {colors:?}",
        sorted_two_sum(&[2, 7, 11, 15], 18),
        max_area_container(&heights)
    );
}

Two-sum: Some((7, 11)), Max container: 49, 3-way partition: [0, 0, 1, 1, 2, 2]