Patterns

Sliding window

A sliding window is a contiguous slice of an array or string. You move the right edge forward one step at a time, and you move the left edge only when the slice stops being valid or when it is longer than you need. The point is to avoid restarting the slice from scratch at every index. Done correctly, each element enters the window once and leaves once, so the whole scan is linear.

The pattern has a prerequisite people skip. Adding an element should change the property you care about in a direction you understand. Fixed-length sums of ordinary numbers have that property. "No repeated id inside the slice" has that property if you track counts. A target sum does not, once negative numbers are allowed, because growing the window can make the sum smaller. That case belongs to prefix sums on the arrays and hashing page. If you are unsure, say so and pick the safer tool.

Windows are also a form of two pointers moving in the same direction. The extra idea is the state you keep inside the slice: a running sum, a count of each item, or a count of how many distinct items you have.

Fixed windows

A fixed window has a length given by the prompt. You fill the first window completely, record its score, then slide: add the new right element, remove the element that fell off the left, and update the score in constant time.

Original task: a list of daily step counts and an integer k. Return the maximum sum of any k consecutive days. If there are fewer than k days, return None. Steps are non-negative, though the algorithm does not need that for a fixed window.

def max_k_day_steps(steps: list[int], k: int) -> int | None:
    if k <= 0 or len(steps) < k:
        return None
    window = sum(steps[:k])
    best = window
    for right in range(k, len(steps)):
        window += steps[right] - steps[right - k]
        best = max(best, window)
    return best


assert max_k_day_steps([1, 3, 2, 5, 1], 3) == 10
assert max_k_day_steps([4, 4], 3) is None
assert max_k_day_steps([2, 2, 2], 3) == 6

Building the first window costs k additions. Each later step costs constant work, and there are n - k of them. Total time is linear in the number of days. Extra space is constant. The naive alternative, summing each window from scratch, is O(n * k). Quote that contrast. It is the reason the pattern exists.

Check the subtraction index. The element leaving the window is at right - k, not right - k + 1. Walk the assert: the first window is 1 + 3 + 2 = 6. The next adds 5 and drops 1, leaving 10. The next adds 1 and drops 3, leaving 8. The best is 10. If your manual walk disagrees with the code, fix the code before you add more features.

k equal to the length of the list is a valid window: the loop does not run and the answer is the total. k equal to 1 is also valid and should return the maximum single day. Add those asserts when you practice. The guard rejects k less than or equal to zero because a window of no days is not a meaningful maximum for this task. Read the prompt before you copy that guard. Some tasks want 0 when k is zero.

Variable windows

A variable window grows and shrinks. You extend right across the sequence. When the window breaks the rule, you advance left until the rule holds again. You update the answer whenever the window is valid. The trick is knowing what "advance left" must repair, and repairing it with the same state you used to detect the break.

Original task: a sequence of error codes. Return the length of the longest contiguous slice that contains no repeated code.

def longest_unique_slice(codes: list[str]) -> int:
    last_index: dict[str, int] = {}
    left = 0
    best = 0
    for right, code in enumerate(codes):
        if code in last_index and last_index[code] >= left:
            left = last_index[code] + 1
        last_index[code] = right
        best = max(best, right - left + 1)
    return best


assert longest_unique_slice(["a", "b", "a", "c"]) == 3
assert longest_unique_slice([]) == 0
assert longest_unique_slice(["z", "z"]) == 1

Each index becomes right once. left only moves forward. The map stores one index per distinct code seen so far. Time is linear. Extra space is proportional to the number of distinct codes in the input, which is at most n.

The condition last_index[code] >= left matters. The map remembers the previous index even after that index has fallen outside the window. If you jump left backward to an old index, you would resurrect codes you have not accounted for. Only a previous sighting that is still inside the window should push left. After the jump, you overwrite the stored index with right, because the newer sighting is the one that matters.

Walk ["a", "b", "a", "c"]. The first a and b grow the window to length 2. The second a was seen at index 0, which is still inside, so left becomes 1. The window is now b, a. Then c extends it to length 3. The best is 3, covering indexes 1 through 3. The duplicate z case never grows past 1, because each new z kicks left to the current index.

This is the same shape you will see on character strings. The strings page uses maps for a different question, anagrams, so do not assume every string task is a window. Ask whether the answer has to be contiguous. If the characters you choose can come from anywhere in the string, you want a frequency map of the whole string, not a window.

When the window is the wrong tool

If the values can be negative and the question is "shortest slice with sum at least target," growing the window can decrease the sum. The "advance left while the sum is too big" story becomes false. Stop and use prefixes, or say that you are switching. Interviewers would rather hear the switch than watch a window produce a confident wrong answer.

If the slice does not have to be contiguous, it is not a window. "Choose any k elements for a maximum sum" is a heap or a sort, depending on the details. The heaps page is the scattered version. Saying "contiguous" in your restatement of the prompt is how you catch this early.

If you need the actual slice and not only its length or sum, store the best left and right indexes whenever you update best. Do not try to rebuild the slice from the map at the end. The map has been overwritten.

Practice drill

Implement the fixed window, then change it to return the starting index of a maximum window, and decide what you should do when two windows tie. The prompt must answer the tie. If it does not, pick the leftmost and say that you are picking it. Then implement the variable window on a string of words instead of codes, with the rule "no repeated word," and add an assert where the repeated word sits outside the current window so the >= left check is actually tested. Finally, write one sentence on paper explaining why you would refuse to use a window if the daily steps could be negative and the task became "sum at least 10." That sentence is the real lesson.