Shrink Until the Window Is Valid

1. Step 1: Seed the empty best window

   Represent the no-solution result as the half-open interval [0, 0]. A valid empty baseline lets later windows replace it only when they are longer.

2. Step 2: Grow a window that stays valid

   Move right forward and record the longest prefix whose sum stays within limit. Nonnegative values make rightward growth monotone until the sum becomes too large.

3. Step 3: Shrink until the sum is valid

   Advance left and subtract leaving values whenever growth exceeds limit. Because values are nonnegative, removing values from the left is the only move that can restore validity while keeping the current right endpoint.

4. Step 4: Preserve the earliest longest window

   Update best only when the current valid window is strictly longer. Replacing on equal length would move the answer right and violate the earliest-tie rule.

• Shrinking only once can leave the window invalid when several outgoing values are needed.
• Updating on equal lengths loses the required earliest-window tie break.
• arrays strings two pointers sliding window

• Python deque Recipes

• Longest Continuous Subarray Within Limit(opens in a new tab)

  Shrink Until the Window Is Valid isolates after shrinking, the current half-open window is valid and no earlier left boundary works for the same right endpoint. That focused state discipline is required when implementing longest continuous subarray limit as a complete Interview Problem.

• Longest Ones After Deleting One Element(opens in a new tab)

  Shrink Until the Window Is Valid isolates after shrinking, the current half-open window is valid and no earlier left boundary works for the same right endpoint. That focused state discipline is required when implementing longest ones after delete as a complete Interview Problem.

• Longest Repeating Character Replacement(opens in a new tab)

  Shrink Until the Window Is Valid isolates after shrinking, the current half-open window is valid and no earlier left boundary works for the same right endpoint. That focused state discipline is required when implementing longest repeating character replacement as a complete Interview Problem.

• Longest Unique-Character Window(opens in a new tab)

  Shrink Until the Window Is Valid isolates after shrinking, the current half-open window is valid and no earlier left boundary works for the same right endpoint. That focused state discipline is required when implementing longest substring without repeating as a complete Interview Problem.

• Max Consecutive Ones III(opens in a new tab)

  Shrink Until the Window Is Valid isolates after shrinking, the current half-open window is valid and no earlier left boundary works for the same right endpoint. That focused state discipline is required when implementing max consecutive ones three as a complete Interview Problem.

• Shortest Subarray With OR at Least K(opens in a new tab)

  Shrink Until the Window Is Valid isolates after shrinking, the current half-open window is valid and no earlier left boundary works for the same right endpoint. That focused state discipline is required when implementing shortest subarray or at least k as a complete Interview Problem.

With nonnegative values, expanding can only increase the sum and moving left can only decrease it, enabling one monotone window. After shrinking, the current half-open window is valid and no earlier left boundary works for the same right endpoint.

Why it works: The right endpoint grows once per iteration, and the left endpoint advances only while the sum limit is violated. The restored window is therefore valid and longest for that right endpoint, so the maximum over endpoints is optimal.

def longest_bounded_window(values, limit):
    left = 0
    total = 0
    best = [0, 0]
    for right, value in enumerate(values):
        total += value
        while left <= right and total > limit:
            total -= values[left]
            left += 1
        if right + 1 - left > best[1] - best[0]:
            best = [left, right + 1]
    return best