Refactoring: Window Shrinking Patterns

The while (sum > S) shrink pattern appears in almost every sliding window problem. Extracting it into a helper makes the intent clear and the code reusable.

The Shrink Pattern

The variable-size window has a repeating structure: extend with right, then shrink with left while a condition is violated, then record the answer.

Before — ad-hoc in main

int left = 0, sum = 0, best = 0;
for (int right = 0; right < n; right++) {
    sum += arr[right];
    while (sum > target) {
        sum -= arr[left];
        left++;
    }
    best = max(best, right - left + 1);
}

After — extracted helper

// C++ — shrink-until pattern extracted
template<typename F>
int max_window(const vector<int>& arr, int target, F should_shrink) {
    int left = 0, sum = 0, best = 0;
    for (int right = 0; right < (int)arr.size(); right++) {
        sum += arr[right];
        while (should_shrink(sum, target)) {
            sum -= arr[left];
            left++;
        }
        best = max(best, right - left + 1);
    }
    return best;
}

// Usage:
int result = max_window(arr, S, [](int sum, int t) {
    return sum > t;
});

Rust: Iterator-Based Approach

Rust's iterators make the shrink pattern even cleaner. The window state can be managed with a fold or scan.

Rust — clean window function

fn max_window(arr: &[i32], target: i32) -> usize {
    let mut left = 0;
    let mut sum = 0;
    let mut best = 0;
    for right in 0..arr.len() {
        sum += arr[right];
        while sum > target {
            sum -= arr[left];
            left += 1;
        }
        best = best.max(right - left + 1);
    }
    best
}

Rust — generic shrink condition

fn max_window_where(
    arr: &[i32],
    mut window: i32,
    mut shrink: impl FnMut(i32, &[i32], usize) -> bool,
) -> usize {
    let mut left = 0;
    let mut best = 0;
    for right in 0..arr.len() {
        window += arr[right];
        while shrink(window, arr, left) {
            window -= arr[left];
            left += 1;
        }
        best = best.max(right - left + 1);
    }
    best
}

Why Extract?

→ The sliding window skeleton is identical for many problems — only the shrink condition changes.
→ Extracting it means you write the loop once and reuse it.
→ max_window_where reads like English: "max window where the sum > target is true".

Key Takeaways

→ The shrink-while pattern is universal in variable-size sliding window.
→ Extract it to make your code declarative: "find the max window where condition holds".
→ C++: template + lambda. Rust: closure + impl FnMut.