Step 6 of 7

Sliding window

A window is a run of consecutive items, v[left..=right]. Many questions are about windows: the best 7-day sales streak, the busiest hour of logs, the longest stretch under budget. Recomputing every window from scratch costs O(n·k) for windows of size k. Sliding the window instead costs O(n): when it moves one step, add the item that enters and remove the item that leaves.

Fixed size

fn main() {
    let visits = [3, 8, 2, 9, 4, 1, 7];
    let k = 3;

    // Simple but recomputes each window: O(n * k)
    let sums: Vec<i32> = visits.windows(k).map(|w| w.iter().sum()).collect();
    println!("{sums:?}");

    // Sliding: add the new item, subtract the one leaving: O(n)
    let mut sum: i32 = visits[..k].iter().sum();
    let mut sliding = vec![sum];
    for right in k..visits.len() {
        sum += visits[right] - visits[right - k];
        sliding.push(sum);
    }
    println!("{sliding:?}");
}

[13, 19, 15, 14, 12]
[13, 19, 15, 14, 12]

windows(k) is great for small k (comparing neighbors with windows(2), for example). For k in the thousands, slide.

Variable size

For "the longest (or shortest) window where some rule holds", grow the window by moving right one step at a time, and shrink it from the left while the rule is broken:

fn longest_within_budget(costs: &[u32], budget: u32) -> usize {
    let mut best = 0;
    let mut left = 0;
    let mut sum = 0;
    for right in 0..costs.len() {
        sum += costs[right];
        while sum > budget {
            sum -= costs[left];
            left += 1;
        }
        best = best.max(right + 1 - left);
    }
    best
}

fn main() {
    let costs = [4, 2, 1, 7, 1, 1, 3, 2];
    println!("{}", longest_within_budget(&costs, 7));
}

4

There's a loop inside a loop, yet it's O(n): left only ever moves forward, so across the whole run the inner while executes at most n times in total. Each item enters the window once and leaves once.

Common mistakes

• if instead of while when shrinking: one step may not be enough to fix the window.
• Negative numbers. Shrinking a window with negative numbers can increase its sum, so the "shrink while too big" logic breaks. Use prefix sums (next step) for those.
• Off by one in the length. With an inclusive right, the window left..=right has right + 1 - left items. Write it in that order: after shrinking, the window can be empty (left == right + 1), and then right - left + 1 panics with attempt to subtract with overflow on usize, while right + 1 - left is simply 0.

Your task

Write fn max_window_sum(values: &[i64], k: usize) -> Option<i64>: the largest total of k consecutive values, or None if k is 0 or larger than the slice. Slide the window. The tests use 200,000 values with k = 100,000, so summing each window from scratch is too slow.

Challenge 2

A fundraiser wants the shortest run of consecutive days whose donations reach a target. Write fn shortest_at_least(values: &[u32], target: u64) -> Option<usize>: the length of the shortest window with a sum of at least target, or None if no window gets there. All values are non-negative, so a variable-size window works: grow it to the right, and while the sum is at least the target, record the length and shrink from the left. The tests have 200,000 values.

Challenge 3

The password checker wants the longest run of characters without a repeat. Write fn longest_unique_run(text: &str) -> usize, counting characters (not bytes). For "abcabcbb" it's 3 ("abc"); for "pwwkew" it's 3 ("wke").

Slide a window over the characters and keep a HashMap<char, usize> of the position where each character was last seen. When the new character was last seen inside the window, move left just past that position. The tests include a 200,000-character text whose longest unique run is 20,000 characters, so restarting from every position is too slow.

Previous: Two pointers Next: Prefix sums