Sliding window cheat sheet

Longest streak of days within a budget

Grow a window one day at a time on the right and keep its total. While the total is over budget, drop days from the left. After each step the window is the longest valid run ending at that day, so the best length seen is the answer. Each day enters and leaves once: O(n) time, O(1) space.

def longest_streak(spend: list[int], budget: int) -> int:
    total = left = best = 0
    for right, x in enumerate(spend):
        total += x
        while total > budget:
            total -= spend[left]
            left += 1
        best = max(best, right - left + 1)
    return best

Longest stretch of a log with no letter seen twice

Slide a window and remember the last index of each character. When the new character was last seen inside the window, jump the left edge just past that index. Every character is processed once, so it is O(n) time and O(k) space for k distinct characters.

def longest_fresh_stretch(log: str) -> int:
    last: dict[str, int] = {}
    left = best = 0
    for right, ch in enumerate(log):
        if last.get(ch, -1) >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

Best total over k consecutive days

Sum the first k days, then slide: add the day entering and subtract the day leaving. Each slide is O(1), so the whole scan is O(n) instead of O(n·k) for re-summing every window. Keep the best total seen. Summing a slice for the first window uses O(k) extra space (an index loop makes it O(1)).

def best_k_days(sales: list[int], k: int) -> int:
    window = sum(sales[:k])
    best = window
    for i in range(k, len(sales)):
        window += sales[i] - sales[i - k]
        best = max(best, window)
    return best

Shortest run of orders that reaches a goal

Grow the window on the right; while its total reaches the goal, record its length and shrink from the left to see if a shorter run still works. Positive values make shrinking monotonic. O(n) time, O(1) space.

def shortest_run(orders: list[int], goal: int) -> int:
    best = 0
    total = left = 0
    for right, x in enumerate(orders):
        total += x
        while total >= goal:
            size = right - left + 1
            best = size if best == 0 else min(best, size)
            total -= orders[left]
            left += 1
    return best

Where does a rearranged pattern appear in a text?

Keep letter counts for a window the size of the pattern. Slide it one character at a time, adding the entering letter and removing the leaving one, and record the start whenever the window's counts equal the pattern's. With a fixed alphabet each comparison is O(1), so the scan is O(n), and the two counters take O(1) space.

Longest single-colour run after repainting k tiles

A window is fixable if its length minus the count of its most common colour is at most k. Grow the window, update counts and the best count seen, and shrink by one when the window is not fixable. The best count never needs to decrease for the answer to stay right, so each step is O(1): O(n) total, with O(c) space for the counts of c colours.

def longest_after_repaints(row: str, k: int) -> int:
    counts: dict[str, int] = {}
    left = top = best = 0
    for right, colour in enumerate(row):
        counts[colour] = counts.get(colour, 0) + 1
        top = max(top, counts[colour])
        if right - left + 1 - top > k:
            counts[row[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Best single buy-then-sell on a price history

Scan the days once, keeping the lowest price seen so far. Each day's best sale is today's price minus that minimum; keep the largest. This is a window whose left edge jumps to any new minimum. O(n) time, O(1) space.

def best_profit(prices: list[int]) -> int:
    best = 0
    low = prices[0] if prices else 0
    for p in prices:
        best = max(best, p - low)
        low = min(low, p)
    return best

Longest stretch with at most two kinds

Keep counts of the kinds inside the window. Add each new item; while more than two kinds are present, remove from the left and delete kinds whose count hits zero. The window is always valid after the loop, so track its best length. O(n) time, O(1) extra space for at most three kinds in the map.

def longest_two_kinds(belt: list[int]) -> int:
    counts: dict[int, int] = {}
    left = best = 0
    for right, kind in enumerate(belt):
        counts[kind] = counts.get(kind, 0) + 1
        while len(counts) > 2:
            old = belt[left]
            counts[old] -= 1
            if counts[old] == 0:
                del counts[old]
            left += 1
        best = max(best, right - left + 1)
    return best

Busiest hour in each k-hour span

Keep a deque of hour indices whose counts are decreasing from front to back. For each new hour, pop smaller counts from the back (they can never be a maximum again), push the hour, and drop the front if it has left the span. The front is always the span's maximum. Each index is pushed and popped once: O(n). The deque holds at most k indexes, so it takes O(k) extra space.

Fixed-size vs variable-size windows

A fixed window has a size given by the question (k items); each step adds one item and removes one. A variable window grows on the right and shrinks on the left until a rule holds again, and the answer is a longest or shortest valid window. Both are O(n) because each item enters and leaves once.

Why a window with a nested loop is still O(n)

Count pointer moves instead of loop iterations. The right pointer moves n times in the for loop; the left pointer only moves forward and never past the right, so across the whole run it moves at most n times. Total work is O(2n) = O(n). This is an amortised argument: one step can do a lot, but the total is bounded.

When a sliding window does not work

Shrinking from the left is only safe if dropping an item always moves the total in one direction. With negative numbers, dropping an item can raise the total, so a window that is too big might become valid by growing. Use prefix sums instead: a run from i to j sums to prefix[j] - prefix[i], and a hash map of earlier prefixes finds matching starts in O(n).