24. Longest Request Window Within a Token Budget

Problem

A serving layer batches consecutive requests from a queue. A contiguous batch is only submittable if the sum of its per-request token costs doesn't exceed a hard per-batch budget.

Given the queue's request costs in order (all non-negative), find the length of the longest contiguous run of requests whose total cost is at most the budget. If no window — not even a single request — fits, return 0.

Source: src/24_sliding_window_token_budget.py

def longest_window_within_budget(costs: list[int], budget: int) -> int:
    ...

Examples:
>>> longest_window_within_budget([1, 1, 1, 1, 10, 1, 1], 4)
4

>>> longest_window_within_budget([3, 3, 3], 2)
0

Step-by-Step Approach

1. Recognize that "longest/shortest contiguous run satisfying a sum constraint, all values non-negative" is the classic variable-size sliding window setup, not something needing prefix sums plus binary search (that's overkill here) or a nested loop (that's O(n²)).
2. Maintain a window with a left and right boundary and a running sum of the elements currently inside it.
3. Expand the window by moving right forward one step at a time, adding each new element's cost to the running sum.
4. Whenever the running sum exceeds the budget, shrink from the left — subtract the leftmost element's cost and advance left — repeating until the sum is back within budget (or the window becomes empty).
5. After each expansion (and any needed shrinking), if the window is non-empty, compare its size to the best length seen so far and keep the larger.
6. Because costs are non-negative, the window's sum only ever increases as it grows and only ever decreases as it shrinks — this monotonicity is what guarantees left never needs to move backward, keeping the whole scan O(n).

The key insight is that non-negative costs make the window sum monotonic in both directions, so left and right can each advance at most n times total across the whole run — no element is ever revisited by the left pointer once passed, which is what makes the amortized cost O(n) instead of O(n²).

Reference solution

def longest_window_within_budget(costs: list[int], budget: int) -> int:
    left = 0
    total = 0
    best = 0
    for right, cost in enumerate(costs):
        total += cost
        # shrink from the left while the window is over budget (costs are non-negative,
        # so removing from the left is the only way to bring the sum back down)
        while total > budget and left <= right:
            total -= costs[left]
            left += 1
        if left <= right:
            best = max(best, right - left + 1)
    return best

Key Functions & Tricks

• Running total updated incrementally — avoids recomputing the window's sum from scratch on every step
• while total > budget: shrink — the core invariant-restoring step; keeps the window valid before measuring its length
• left <= right guard — distinguishes a genuinely empty window (when even one element blows the budget) from a valid one-element window
• right - left + 1 — window length from its two boundary indices
• Two pointers, each only ever moving forward — the structural reason this is O(n) instead of O(n²)

How to Recognize This Pattern