Two pointers and windows

Sit by the window of a moving train. You never see the whole countryside at once. You see one frame of it, and as the train moves, a new field enters on the right while an old one slips off on the left.

That is the sliding window. It is a stretch of neighbouring items in a list, and it moves along one step at a time. Its sibling is two pointers: two markers that walk through the same list, usually from opposite ends or one behind the other. A pointer here is only a number saying "I am at this position", the kind of index you met in lesson 1.

Both tricks replace a slow habit. The slow habit is to check every pair, or every stretch, with a loop inside a loop. That costs O(n²). These two keep a little state as they walk, and each marker only ever moves forward. So the whole job costs O(n), one trip through the data.

Reach for them when a problem talks about a pair that adds up to something, a stretch of neighbours ("subarray" or "substring"), or the longest or biggest such stretch.

The window. Take six daily sales, 2, 1, 5, 1, 3 and 2, and ask: what is the best total over any three days in a row? The slow way adds up three numbers for every starting day. The window way adds up the first three once: 2 + 1 + 5 = 8. To slide one day, the 1 on the right comes in and the 2 on the left leaves, so the new total is 8 − 2 + 1 = 7. Two small changes, not three additions. Keep going, and the best total is 9, for 5 + 1 + 3.

That is a fixed window, because its size stays at three. A growing and shrinking window is trickier, and more powerful. The rule is: grow on the right, and when the window breaks a rule, shrink from the left until it is fine again. Say you have a budget, and you want the most days in a row that cost no more than 6 in total. Extend the right edge, add the day's cost, and if you went over the budget, drop days from the left until you are back under. Each day enters once and leaves at most once, so it is still one trip.

Two pointers from both ends. Say you have sorted prices and want two that add up to 18. Put one marker at the cheapest price, and one at the dearest. Add them. If the total is too small, the left price is hopeless: even with the biggest partner, it is too small. So move the left marker right. If the total is too big, the right price is hopeless even with the smallest partner, so move the right marker left. Each step throws away one price for good. The markers meet in the middle, and you have checked the whole list in one pass.

This works because the list is sorted. Without that, "too small" would not tell you which way to go.

Remember: a sliding window updates its total with what comes in and what leaves. Two pointers need a reason to move, and the reason is always "this one cannot be part of an answer".

First, a pair that adds up to a target, in a sorted slice.

use std::cmp::Ordering;

/// In a sorted slice, finds two different positions whose values add up to
/// `target`. One pointer starts at each end and they walk towards each other.
pub fn pair_with_sum(sorted: &[i32], target: i32) -> Option<(usize, usize)> {
    if sorted.is_empty() {
        return None;
    }
    let (mut left, mut right) = (0, sorted.len() - 1);
    while left < right {
        match (sorted[left] + sorted[right]).cmp(&target) {
            Ordering::Equal => return Some((left, right)),
            // Too small: the left value cannot work with anything, since
            // `right` already holds the biggest value still in play.
            Ordering::Less => left += 1,
            // Too big: the right value is too large even with the smallest.
            Ordering::Greater => right -= 1,
        }
    }
    None
}

left and right start at the two ends. The match compares the sum with the target using cmp, which gives back an Ordering: less, equal or greater. Equal means done. Less moves left up. Greater moves right down. The loop condition left < right makes sure the two markers never point at the same item, so an item cannot pair with itself. It returns the positions, not the values.

Now the fixed window.

/// The biggest total of any `k` neighbours in a row, or `None` if there are
/// not `k` numbers.
pub fn best_window_sum(nums: &[i32], k: usize) -> Option<i32> {
    if k == 0 || k > nums.len() {
        return None;
    }
    let mut sum: i32 = nums[..k].iter().sum();
    let mut best = sum;
    for end in k..nums.len() {
        // Slide by one: the new number comes in and the oldest one leaves.
        // That is two steps, instead of adding up all `k` numbers again.
        sum += nums[end] - nums[end - k];
        best = best.max(sum);
    }
    Some(best)
}

The first k numbers are added once, with nums[..k].iter().sum(). Then each step adds the number entering at end and takes away the one leaving, which sits k places behind. A guard at the top handles a window of 0 or one that is longer than the list.

Remember: to slide a fixed window, add the new one and subtract the old one.

Last, the stretchy window.

/// The most days in a row whose costs add up to no more than `budget`.
/// The window grows on the right and shrinks on the left.
pub fn longest_within_budget(costs: &[u32], budget: u32) -> usize {
    let (mut start, mut total, mut best) = (0, 0, 0);
    for end in 0..costs.len() {
        total += costs[end]; // let the window grow

        // Too expensive: drop days from the left until it fits again.
        while total > budget {
            total -= costs[start];
            start += 1;
        }
        best = best.max(end + 1 - start);
    }
    best
}

start and end are the two edges. Each trip around the loop pushes end one step right and adds that day's cost. The inner while then shrinks the window from the left until the total fits. A while, not an if, because one expensive day may need several cheap days to leave. Afterwards, the window is start..=end, which has end + 1 - start days, and best remembers the biggest.

If a single day costs more than the whole budget, the window shrinks all the way to empty. That is fine, and the length is 0 for that step.

Slices have helpers for this. The Playground link on this one runs it.

let sales = [2, 1, 5, 1, 3, 2];

// `windows(3)` hands out every run of 3 neighbours, one step apart.
let best = sales.windows(3).map(|w| w.iter().sum::<i32>()).max();
println!("{:?}", best);
assert_eq!(best, Some(9));

// Windows of 2 compare each item with the next one.
let in_order = |items: &[i32]| items.windows(2).all(|pair| pair[0] <= pair[1]);
assert!(in_order(&[1, 2, 2, 5]));
assert!(!in_order(&[1, 3, 2]));

// `chunks(2)` cuts into separate pieces, with no overlap.
let pieces: Vec<&[i32]> = sales.chunks(4).collect();
assert_eq!(pieces, [&[2, 1, 5, 1][..], &[3, 2][..]]);

• windows(k) hands out every run of k neighbours, one step apart, and the runs overlap. It is the sliding window as an iterator. It is neat, but it adds up all k numbers every time, so the cost is O(n × k), not O(n). For a small k that is fine. For a huge window, use the add-and-subtract loop above.
• windows(2) pairs each item with the next. With all, it checks whether a slice is sorted, in one line.
• chunks(k) cuts the slice into separate pieces of k, with no overlap. The last piece may be shorter.

For two pointers, there is nothing special in the library. Two usize variables are all you need. If you want to walk from both ends over a slice of items, iter() has a rev() that reads backwards, and you can combine the two with zip.

Remember: windows for a quick answer on a short window, a hand-rolled loop for the fast one.

If the slice is not sorted, sorting first costs O(n log n). That is still far better than O(n²).

Each starter has a todo!(), a placeholder that panics if it runs. Replace it with your code.

pub fn is_palindrome(text: &str) -> bool {
    todo!("one pointer at each end, walking inwards")
}

/// Reads the same both ways, ignoring spaces, punctuation and capitals.
/// Works on plain English (ASCII) text.
pub fn is_palindrome(text: &str) -> bool {
    let bytes = text.as_bytes();
    if bytes.is_empty() {
        return true;
    }
    let (mut left, mut right) = (0, bytes.len() - 1);
    while left < right {
        if !bytes[left].is_ascii_alphanumeric() {
            left += 1; // skip a space or comma
        } else if !bytes[right].is_ascii_alphanumeric() {
            right -= 1;
        } else if !bytes[left].eq_ignore_ascii_case(&bytes[right]) {
            return false;
        } else {
            left += 1;
            right -= 1;
        }
    }
    true
}

pub fn most_water(heights: &[u32]) -> u32 {
    todo!("which pointer should move?")
}

/// Two walls at positions `i` and `j` hold water as wide as the gap and as
/// high as the shorter wall. Returns the most any pair can hold.
pub fn most_water(heights: &[u32]) -> u32 {
    if heights.is_empty() {
        return 0;
    }
    let (mut left, mut right) = (0, heights.len() - 1);
    let mut best = 0;
    while left < right {
        let width = (right - left) as u32;
        best = best.max(width * heights[left].min(heights[right]));

        // The shorter wall is the limit. Moving the taller one in can only
        // make the gap narrower with the same limit, so move the shorter.
        if heights[left] < heights[right] {
            left += 1;
        } else {
            right -= 1;
        }
    }
    best
}

pub fn longest_unique(text: &str) -> usize {
    todo!("a window that never holds a repeat")
}

use std::collections::HashMap;

/// The length of the longest run of letters with no letter repeated.
pub fn longest_unique(text: &str) -> usize {
    let mut last_seen: HashMap<char, usize> = HashMap::new();
    let (mut start, mut best) = (0, 0);

    for (end, letter) in text.chars().enumerate() {
        // If this letter is already in the window, jump past its old spot.
        if let Some(&old) = last_seen.get(&letter) {
            if old >= start {
                start = old + 1;
            }
        }
        last_seen.insert(letter, end);
        best = best.max(end + 1 - start);
    }
    best
}

Two pointers and the sliding window are favourites because the brute force is easy and the clean answer takes one good idea.

• Spot the signals. "Subarray", "substring", "contiguous", "longest", "shortest", "at most k", and "a pair that sums to" are the usual words. A sorted input with a pair question is almost always two pointers.
• Start with the slow answer. Say "the brute force checks every pair in O(n²)". Then explain the observation that lets one marker move without looking back. That story is the answer.
• Name the rule for moving. For two pointers, say why you move each side ("too small, so this left value cannot work"). For a window, say what rule it must satisfy, and what you do when it breaks.
• Decide the window type. A fixed size means add and subtract. A "longest" or "shortest" with a rule means grow right and shrink left.
• Explain the nested loop. If you write a while inside a for, say why it is still O(n): each marker only moves forward.
• Say what you track. A running total, a map of letter counts, or the last place each letter was seen. Name the state, and the space cost.
• Watch the edges. An empty slice, a window larger than the list, one item, and a single item that already breaks the rule. In Rust, take care with len() - 1 on an empty slice, which underflows and panics.

Made by VeraStack Labs