Sliding window

A sliding window reuses work between neighboring ranges. For a window of fixed size k, add the number that enters and subtract the one that leaves. That gives the sum of every k-length range in O(n) time and O(1) extra space, even with negative numbers.

A window that grows and shrinks needs more: a reason each end can move forward and never come back. Say every number is positive and you want the shortest range with sum at least a target. Moving right raises the sum, and moving left lowers it. Whenever the sum is big enough, record the length and shrink from the left. Once a start position has found a valid window, a later end can't give that start a shorter one.

pub fn min_len_positive(nums: &[i32], target: i64) -> Option<usize> {
    assert!(target > 0 && nums.iter().all(|&x| x > 0));
    let (mut left, mut sum) = (0_usize, 0_i64);
    let mut best = None;
    for (right, &x) in nums.iter().enumerate() {
        sum += i64::from(x);
        while sum >= target {
            let len = right - left + 1;
            best = Some(best.map_or(len, |old: usize| old.min(len)));
            sum -= i64::from(nums[left]);
            left += 1;
        }
    }
    best
}

Each number enters once and leaves at most once, so both loops together cost O(n). sum always equals the window's sum. And for every start that left has moved past, best already includes its shortest valid window. An empty list returns None.

For [2, 3, 1, 2, 4, 3] and target 7, the first valid window has length 4. Later, shrinking [2, 4, 3] gives [4, 3], which improves the answer to 2. Draw both pointers as they move: neither ever goes back.

This breaks on [1, -1, 5] with target 5. After the whole list reaches 5, removing 1 drops the sum to 4, so the window stops shrinking and misses [5]. Negative numbers don't break every sliding window. They break this one, because "a bigger window has a bigger sum" no longer holds.

For the longest substring without repeated characters, track character counts and shrink until the repeat is gone. Adding characters can't remove a repeat, but removing enough characters can. For the minimum window containing a set of characters, track how many of each you still need. Shrink while the window still covers everything, and record the answer before the window stops covering.

Practice: LC 643 Maximum Average Subarray I, LC 209 Minimum Size Subarray Sum, LC 3 Longest Substring Without Repeating Characters, LC 424 Longest Repeating Character Replacement, LC 76 Minimum Window Substring. LC 424 has a clever optimization that keeps a stale count. Skip it until you can prove the simpler version works.

Check your understanding: Is the window fixed or growing and shrinking? Why does growing a window keep it valid, or keep it invalid? When should you record the answer: before shrinking, while shrinking, or after?