RustArena

Step 5 of 7

Two pointers

Many problems that look like "check every pair" (O(n²)) can be solved with two indices that move through the data in a smart way, touching each item once: O(n) time and O(1) extra memory. Three common patterns:

  1. From both ends (on sorted data or symmetric questions): i starts at the front, j at the back, and each step moves one of them inward.
  2. Read and write (same direction): read visits every item, write marks where the next kept item goes. That's how you filter in place.
  3. Two sequences: one index per sequence, like the merge in merge sort.

Checking a palindrome from both ends, ignoring case and punctuation:

fn is_palindrome(text: &str) -> bool {
    let letters: Vec<char> = text
        .chars()
        .filter(|c| c.is_alphanumeric())
        .map(|c| c.to_ascii_lowercase())
        .collect();
    if letters.is_empty() {
        return true;
    }
    let (mut i, mut j) = (0, letters.len() - 1);
    while i < j {
        if letters[i] != letters[j] {
            return false;
        }
        i += 1;
        j -= 1;
    }
    true
}

fn main() {
    for s in ["Never odd or even", "Rust", "A man, a plan, a canal: Panama"] {
        println!("{s:?}: {}", is_palindrome(s));
    }
}

"Never odd or even": true
"Rust": false
"A man, a plan, a canal: Panama": true

The chars are collected into a Vec<char> first because a &str can't be indexed by position (UTF-8, remember).

Read and write pointers, removing the zero readings from a Vec in place:

fn remove_zeros(v: &mut Vec<i32>) {
    let mut write = 0;
    for read in 0..v.len() {
        if v[read] != 0 {
            v[write] = v[read];
            write += 1;
        }
    }
    v.truncate(write);
}

fn main() {
    let mut readings = vec![0, 4, 0, 0, 7, 2, 0];
    remove_zeros(&mut readings);
    println!("{readings:?}");
}

[4, 7, 2]

That's what v.retain(|&x| x != 0) does inside; in real code, call retain. Calling v.remove(i) for each zero instead would shift the rest of the Vec every time: O(n²).

Why "from both ends" works on sorted data

Looking for two numbers in a sorted slice that add up to a target: start with the smallest (i) and the largest (j). If their sum is too small, the smallest can't be part of any answer (even the largest partner isn't enough), so move i right. If the sum is too big, the largest can't be part of any answer, so move j left. Each step rules out one item for good.

Common mistakes

Your task

Write fn pair_with_sum(sorted: &[i32], target: i32) -> Option<(usize, usize)> that returns the indices (i, j), i < j, of two items of the sorted slice that add up to target, or None. Use two pointers from both ends, with no HashMap (O(1) extra memory). In every test at most one pair works. The tests include a slice of 200,000 numbers.

Challenge 2

Write fn dedup_sorted(v: &mut Vec<i32>) that removes repeated values from a sorted Vec in place, keeping one of each, with read and write pointers. No dedup, retain, remove or sets. The tests include 200,000 copies of the same value, where calling remove for each repeat would be O(n²).

Challenge 3

A city builds a reservoir between two of the walls along a valley. walls[i] is the height of wall i, and walls are one unit apart. Water between walls i < j fills up to the lower wall: the amount is min(walls[i], walls[j]) * (j - i). Write fn max_water(walls: &[u32]) -> u64: the most water any pair of walls can hold (0 with fewer than two walls).

Start with the two outermost walls. Then move the pointer at the lower wall inward: keeping the lower wall can never do better, because any pair using it is narrower and still limited by its height. The tests have 100,000 walls.

Previous: Implementing sorts: insertion sort and merge sort Next: Sliding window