Pattern1 Practice6 Interview

Variable-size Window

GuideCode Labs

Expand and contract a window to preserve a validity invariant and optimize its length or score. Learn its decision rule, maintained state, Python cost model, and transfer from a focused drill to a full Interview Problem.

Recognize it when

Consider Variable-size Window when the prompt's constraints and required operations match this shape: Expand and contract a window to preserve a validity invariant and optimize its length or score.

On this page · Let Validity Control the Left Edge

Checking your account…

Let Validity Control the Left Edge

A variable window grows right to discover candidates and moves left only to restore or tighten a monotone constraint. The state always describes one contiguous interval.

Expand Right Exactly Once

Each input element enters when right reaches it. Update the sum or frequency state immediately, then evaluate whether the window remains valid.

Trace Variable Window Boundaries

Reference

def bounded_window_trace(values, limit):
    left = total = 0
    trace = []
    for right, value in enumerate(values):
        total += value
        while total > limit and left <= right:
            total -= values[left]
            left += 1
        trace.append([left, right, total])
    return trace

Practice

Implement bounded_window_trace(values, limit). For nonnegative values, return [left, right, sum] after shrinking each right-expanded window to sum at most limit.

def bounded_window_trace(values, limit):
    pass

Public tests

Restore validity after expansion

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Shrink Until the Invariant Returns

Use while, not if, when several left elements may need to leave. For longest-valid problems, measure after validity returns; for minimum windows meeting a target, measure before each shrink while the target remains satisfied.

Find Minimum Window Reaching a Target

Reference

def min_window_at_least(values, target):
    left = total = 0
    best = len(values) + 1
    for right, value in enumerate(values):
        total += value
        while total >= target:
            best = min(best, right - left + 1)
            total -= values[left]
            left += 1
    return 0 if best > len(values) else best

Practice

Implement min_window_at_least(values, target). values contains positive integers. Return the minimum contiguous length with sum at least target, or 0.

def min_window_at_least(values, target):
    pass

Public tests

Shrink while the target remains met

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Know When Monotonicity Fails

Sum-based shrinking relies on nonnegative values: removing from the left cannot increase the sum. With negative values, prefix sums plus hashing, a deque, or another technique may be required. Each boundary moves at most n times, so valid monotone scans are O(n).

Explain It in an Interview

Say: “Right enters once; left advances only while this monotone condition permits it. My summary describes exactly the current boundaries.” State whether the objective is longest valid or shortest sufficient before placing the answer update.

Python Version Note

Python 3.11+

The examples use the standard Python syntax and containers supported by the browser Judge; the Variable-size Window invariant is independent of a minor Python release.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Variable-size Window decision loop	`O(n)`	`O(n)`	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.

Space

O(1) excluding the returned pair for the focused Shrink Until the Window Is Valid implementation.

Assumptions

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.
The bound includes real Python operations; no repeated slicing, linear list membership, or hidden sorting is treated as free.

Invariants Worth Saying Aloud

State the precise Variable-size Window invariant before coding and preserve it after every update, traversal step, or recursive return.
After the shrink loop, the current window satisfies the validity rule.
Left and right boundaries move only forward.
With nonnegative values, expanding can only increase the sum and moving left can only decrease it, enabling one monotone window. Preserve this property after every transition.
After shrinking, the current half-open window is valid and no earlier left boundary works for the same right endpoint. Preserve this property after every transition.

When To Use Or Avoid Variable-size Window

Use It When

Use Variable-size Window when the prompt exposes the ordering, monotonicity, recurrence, or constraint that makes this decision safe.
Use it when after the shrink loop, the current window satisfies the validity rule.

Choose Another Tool When

Avoid Variable-size Window when its decision rule cannot eliminate work or preserve the required state.
Avoid forcing the label onto a prompt whose simpler direct scan already meets the constraints.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Moving state without a proof

Applying the pattern without proving its ordering, monotonicity, or window invariant can silently miss valid candidates.

Prevent it: Write the decision rule beside the loop and verify it against Shrink Until the Window Is Valid before optimizing.

Avoid

def longest_bounded_window(values, limit):
    pass

Use instead

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

Where you will hit this: Shrink Until the Window Is Valid(opens in a new tab)

Breaking the maintained state

Overwrites the best window on equal length and therefore loses the required earliest-window tie break.

Prevent it: Use the public tests and preserve this state: After the shrink loop, the current window satisfies the validity rule.

Avoid

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

Use instead

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

Where you will hit this: Shrink Until the Window Is Valid(opens in a new tab)

Hiding Python work in the hot path

Python slicing, copying, membership in lists, or repeated sorting inside the loop can invalidate the intended complexity.

Prevent it: Count every slice, copy, sort, membership check, and container update before claiming O(n).

Avoid

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

Use instead

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

Where you will hit this: Longest Continuous Subarray Within Limit(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python deque Recipes(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…