Variable-size window

A variable-size window has two pointers, left and right, that both only move forward. The right pointer adds elements; the left pointer removes them. The window's length changes as the scan goes.

It answers questions like 'shortest subarray with sum at least target' or 'longest substring with at most k zeros'. The key requirement is monotonic validity: making the window bigger moves it in one direction only (for example, the sum only goes up because all numbers are positive), so once you shrink past a point you never need to come back to it.

1. 1Start with left = 0 and an empty window state (a sum, a count of zeros, a map of counts).
2. 2Move right from 0 to n-1. Each step, add nums[right] to the state.
3. 3Shortest-valid problems: while the window is valid, record its length, then remove nums[left] and move left forward. You keep shrinking to find the smallest valid window ending at right.
4. 4Longest-valid problems: while the window is invalid, remove nums[left] and move left forward. Once valid again, record the length.
5. 5Because left only moves forward and never passes right by more than one, the inner while loop runs at most n times in total across the whole scan. That makes the total O(n), even though there is a loop inside a loop.

def min_subarray_len(target, nums):
    """Length of the shortest subarray with sum >= target.
    Requires all numbers to be positive."""
    left = 0
    window = 0
    best = float("inf")
    for right, x in enumerate(nums):
        window += x                       # grow: take nums[right]
        while window >= target:           # valid: record, then shrink
            best = min(best, right - left + 1)
            window -= nums[left]
            left += 1
    return 0 if best == float("inf") else best


def longest_ones(nums, k):
    """Longest run of 1s if you may flip at most k zeros."""
    left = zeros = best = 0
    for right, x in enumerate(nums):
        zeros += (x == 0)
        while zeros > k:                  # invalid: shrink until valid
            zeros -= (nums[left] == 0)
            left += 1
        best = max(best, right - left + 1)  # record after fixing
    return best

Both functions are O(n) time and O(1) space because left only moves forward. Note where the answer is recorded: inside the shrinking loop for 'shortest valid', after it for 'longest valid'.

Cost: Time O(n): each index enters once and leaves at most once (amortised). Space O(1) for sums and counters, O(distinct values) if you keep a map.