Window Shrinking

Shrinking moves L forward to discard stale data once the window is too fat or invalid. It restores feasibility so R can continue scanning.

Why this shows up in the real world

Call center SLAs shrink the open-case window when too many unresolved tickets pile up—operations “tighten” scope. Cache eviction shrinks resident set when memory pressure hits.

Core idea (explained for students)

While loop is your friend: while not valid: update state removing s[L]; L += 1. Ensure progress—each iteration should increase L or break.

Try this in Python

def shrink_to_sum_leq(nums: list[int], budget: int) -> int:
    s, L, best = 0, 0, 0
    for R, x in enumerate(nums):
        s += x
        while s > budget and L <= R:
            s -= nums[L]
            L += 1
        best = max(best, R - L + 1)
    return best


print(shrink_to_sum_leq([1, 2, 3, 4, 5], 7))

Common mistakes

• Shrinking without removing the left character from aggregates.
• Shrinking past R—empty window edge cases.

Key takeaways

• Pair every R++ with a tightening while-loop when needed.
• Log L,R,state on failing tests.