The Sliding Window Technique in Python: Subarray Problems Made Linear

A list of 100,000 numbers contains 5,000,050,000 contiguous runs. If your first instinct for "find the best subarray" is to look at each of them, you have written an algorithm that will not finish this afternoon. A sliding window answers the same question in fewer than 200,000 steps, because it never touches any element more than twice: once when it joins the window, once when it leaves.

A window is just a contiguous run, held by two indices: left and right. The technique is a rule about how those indices are allowed to move. The right edge steps forward and one element joins the window. The left edge steps forward and one element leaves. Nothing else ever happens, neither edge ever goes backwards, and the quantity you care about — a sum, a character count, a set of distinct values — is patched up as elements join and leave instead of being recomputed from the elements still inside.

Two things about this pattern get skipped almost everywhere, and both are here. The first is why the variable-size version is still linear despite having a while loop nested inside a for loop, which looks quadratic and is not. The second is the precondition: sliding windows are only correct when shrinking from the left can actually repair an invalid window. Break that condition — an array containing negative numbers is the standard way to break it — and the algorithm does not crash, it just returns the wrong answer.

The idea

Fixed-size windows: add one, remove one

Start with the simplest version, where the width is handed to you. Given the readings [2, 1, 5, 1, 3, 2], what is the largest sum of 3 consecutive values?

The obvious approach adds up each window from scratch. There are n - k + 1 windows of width k in a list of n values, and each one costs k reads, so the bill is (n - k + 1) * k reads. For n of 100,000 and k of 1,000 that is 99,001,000 reads to answer one question about a list you could scan nine hundred and ninety times over in the same effort.

The waste is obvious once you line two neighbouring windows up. The window at indices 1 to 3 shares indices 1 and 2 with the window at indices 0 to 2. Only one value left and one value arrived. So carry the sum forward:

• subtract the value that just fell off the left edge,
• add the value that just arrived at the right edge.

Two operations per step, regardless of how wide the window is.

Variable-size windows: expand, then shrink

Most real problems do not tell you the width. Instead they give you a rule the window must obey — no repeated characters, at most 2 distinct values, a sum no greater than 10 — and ask for the longest (or shortest) run that obeys it.

The loop is always the same three steps:

1. Move right forward by one. The new element joins the window.
2. While the window breaks the rule, move left forward by one, evicting the leftmost element.
3. The window is valid again. Record it if it beats the best seen so far.

Step 2 is where the correctness lives, and it rests on one assumption that is worth stating out loud because almost nobody does:

If a window is invalid, every window that contains it is invalid too.

That is the monotonicity precondition, and it does two separate jobs. For a fixed right edge it makes validity a threshold: there is some index where the window becomes valid, everything at or after it is valid, and everything before it is not — so shrinking is guaranteed to reach that threshold rather than overshooting past it. For a fixed left edge it says an invalid window cannot be rescued by taking in more on the right, and that is what lets left stay put: once a left edge has been evicted, no window starting there will ever be valid again, at any later right edge. Both halves are needed, and both fall out of the one sentence above.

Check it on "no repeated characters": if a run contains two copies of the letter a, then any longer run containing it also contains both copies, so it is invalid too. It holds. Check it on "sum at most 10" with non-negative values: adding values on either side can only make the sum bigger, never smaller, so a run that is already over the limit stays over. It holds — as long as the values are non-negative. Hold that thought.

Watching it work

The fixed window, by hand

Take [2, 1, 5, 1, 3, 2] with k of 3. The first window is added up in full; every window after that is one subtraction and one addition.

The answer is 9. The whole list was read once, plus three extra reads for the values leaving — 9 reads against the brute force's 12. At six elements that is a shrug. At 100,000 elements with k of 1,000 it is 199,000 reads against 99,001,000.

The variable window, by hand

Now the harder shape. Find the length of the longest substring of "abcabcbb" with no repeated character.

Keep a dict last_seen mapping each character to the most recent index it appeared at, and a start index for the left edge. For each character you read, if it was last seen inside the current window, the left edge jumps to just past that earlier copy. That is a shrink of several positions in one move, which is fine — left only ever goes forward.

• i=0, read a. Window "a", length 1.
• i=1, read b. Window "ab", length 2.
• i=2, read c. Window "abc", length 3. Best so far.
• i=3, read a. Last seen at index 0, which is inside the window, so start jumps to 1. Window "bca", length 3.
• i=4, read b. Last seen at index 1, inside. start jumps to 2. Window "cab".
• i=5, read c. Last seen at index 2, inside. start jumps to 3. Window "abc".
• i=6, read b. Last seen at index 4, inside. start jumps to 5. Window "cb", length 2.
• i=7, read b. Last seen at index 6, inside. start jumps to 7. Window "b", length 1.

The answer is 3. Count the movement: the right edge took eight steps, and the left edge moved on five of those steps, travelling 0 to 1 to 2 to 3 to 5 to 7 — seven positions in total. Fifteen moves for an eight-character string, against a ceiling of 2n = 16. No substring was ever built or rescanned.

The code

The naive fixed-size version first, so there is something honest to compare against.

def max_sum_naive(values: list[int], k: int) -> int:
    """Largest sum of k consecutive values, recomputing every window in full."""
    if not 1 <= k <= len(values):
        raise ValueError("k must be between 1 and len(values)")

    best = sum(values[0:k])
    for start in range(1, len(values) - k + 1):
        best = max(best, sum(values[start:start + k]))
    return best


readings = [2, 1, 5, 1, 3, 2]
print(max_sum_naive(readings, 3))

9

Correct, and it re-reads k values every step for no reason. The window version keeps the running sum instead.

def max_sum_window(values: list[int], k: int) -> int:
    """Largest sum of k consecutive values, in a single pass.

    The first window is added up in full. After that each step adds the value
    entering on the right and subtracts the one leaving on the left, so keeping
    the sum correct costs two operations no matter how wide the window is.
    """
    if not 1 <= k <= len(values):
        raise ValueError("k must be between 1 and len(values)")

    # Summed by index rather than sum(values[:k]) so that no k-element slice is
    # ever built; the whole point is that this function holds nothing but a total.
    window_sum = sum(values[index] for index in range(k))
    best = window_sum

    for right in range(k, len(values)):
        window_sum += values[right] - values[right - k]
        best = max(best, window_sum)

    return best


print(max_sum_window(readings, 3))
print(max_sum_window([7], 1), max_sum_window([-4, -1, -9], 2))

9
7 -5

The gap between them is arithmetic, not opinion. The naive version reads (n - k + 1) * k values; the window version reads k for the first window and 2 for every step after.

print(f"{'n':>9} {'k':>7} {'naive reads':>15} {'window reads':>13}")
for size, width in [(1_000, 100), (100_000, 1_000), (1_000_000, 10_000)]:
    naive_reads = (size - width + 1) * width
    window_reads = width + 2 * (size - width)
    print(f"{size:>9,} {width:>7,} {naive_reads:>15,} {window_reads:>13,}")

        n       k     naive reads  window reads
    1,000     100          90,100         1,900
  100,000   1,000      99,001,000       199,000
1,000,000  10,000   9,900,010,000     1,990,000

Now the variable-size version, plus a traced copy that prints the walkthrough above so you can check the hand trace against the machine.

def longest_unique(text: str) -> int:
    """Length of the longest substring of text with no repeated character.

    last_seen maps a character to the most recent index it appeared at. When
    the character entering on the right is already inside the window, the
    window's left edge jumps to just past that earlier copy.
    """
    last_seen: dict[str, int] = {}
    start = 0
    best = 0

    for index, character in enumerate(text):
        previous = last_seen.get(character, -1)
        if previous >= start:
            # The repeat is inside the window, so every window that keeps both
            # copies is invalid. Skip left past the older one in one move.
            start = previous + 1
        last_seen[character] = index
        best = max(best, index - start + 1)

    return best


def longest_unique_traced(text: str) -> int:
    """The same algorithm, printing the window after every character read."""
    last_seen: dict[str, int] = {}
    start = 0
    best = 0
    for index, character in enumerate(text):
        previous = last_seen.get(character, -1)
        moved = ""
        if previous >= start:
            start = previous + 1
            moved = f"repeat at {previous}, start jumps to {start}"
        last_seen[character] = index
        best = max(best, index - start + 1)
        line = (f"i={index} read {character}  window [{start}:{index + 1}]"
                f" = {text[start:index + 1]:<4} best={best}")
        print(line + f"  {moved}" if moved else line)
    return best


print(longest_unique_traced("abcabcbb"))

i=0 read a  window [0:1] = a    best=1
i=1 read b  window [0:2] = ab   best=2
i=2 read c  window [0:3] = abc  best=3
i=3 read a  window [1:4] = bca  best=3  repeat at 0, start jumps to 1
i=4 read b  window [2:5] = cab  best=3  repeat at 1, start jumps to 2
i=5 read c  window [3:6] = abc  best=3  repeat at 2, start jumps to 3
i=6 read b  window [5:7] = cb   best=3  repeat at 4, start jumps to 5
i=7 read b  window [7:8] = b    best=3  repeat at 6, start jumps to 7
3

How the code maps to the idea

values[right] - values[right - k] is the add-one-remove-one update, written as a single expression. When the right edge sits at index right, the window covers the k indices ending there, so the value that just fell out is exactly k positions back. Getting that offset wrong by one is the classic bug in this line, and it does not raise — it silently sums the wrong window.

The first window is summed in full, outside the loop. That is the only place sum() appears. If you see sum() inside the loop, the running total is not running and the algorithm is back to quadratic.

if previous >= start is the guard that makes the left edge one-directional. Without it, start is set to previous + 1 whenever the character has ever been seen, including when that sighting was before the current window — which drags the left edge backwards and invents substrings that were never valid. The shortest input that exposes it is "abba":

def longest_unique_unguarded(text: str) -> int:
    """The same code with the `previous >= start` guard removed."""
    last_seen: dict[str, int] = {}
    start = 0
    best = 0
    for index, character in enumerate(text):
        if character in last_seen:
            start = last_seen[character] + 1
        last_seen[character] = index
        best = max(best, index - start + 1)
    return best


def longest_unique_brute(text: str) -> int:
    """Check every substring. Used only to confirm the fast version."""
    best = 0
    for start in range(len(text)):
        for end in range(start + 1, len(text) + 1):
            piece = text[start:end]
            if len(set(piece)) == len(piece):
                best = max(best, end - start)
    return best


for sample in ["abba", "abcabcbb", "pwwkew", "bbbbb", ""]:
    print(f"{sample!r:<10} window={longest_unique(sample)} "
          f"unguarded={longest_unique_unguarded(sample)} "
          f"brute={longest_unique_brute(sample)}")

'abba'     window=2 unguarded=3 brute=2
'abcabcbb' window=3 unguarded=3 brute=3
'pwwkew'   window=3 unguarded=3 brute=3
'bbbbb'    window=1 unguarded=1 brute=1
''         window=0 unguarded=0 brute=0

Trace "abba" to see it. At i=2 the second b arrives, so start moves to 2 and the window is "b". At i=3 the a arrives; it was last seen at index 0, which is behind the left edge, so it is not in the window at all and nothing should move. The unguarded version sets start back to 1, claims the window "bba" has length 3, and reports 3 for a string whose answer is 2. Every other test agrees, which is exactly why this bug survives code review.

Edge cases fall out of the arithmetic. An empty string never enters the loop and returns 0. A string of identical characters shrinks on every step and returns 1. In the fixed-size version, k equal to len(values) gives an empty range(k, len(values)), so the initial sum is the answer.

Two more windows worth memorising

Minimum window substring

Given a text and a target, find the shortest substring of the text containing every character of the target, counting repeats. This is the problem that teaches the need/have counter: a dict of required counts, a dict of current counts, and a single integer matched recording how many distinct required characters are currently present at full strength. The window is valid exactly when matched equals the number of distinct characters in the target — one integer comparison, not a dict comparison.

There is one structural difference from every window so far. For a longest answer you shrink until the window is valid, then record. For a shortest answer you record while the window is still valid, then shrink to try for better. Same loop, opposite placement of the recording line.

def min_window(text: str, target: str) -> str:
    """Shortest substring of text containing every character of target.

    need holds the required count of each character. matched counts how many
    distinct required characters currently sit in the window at full strength,
    so the window is valid exactly when matched equals len(need).
    """
    if not target or len(target) > len(text):
        return ""

    need: dict[str, int] = {}
    for character in target:
        need[character] = need.get(character, 0) + 1

    have: dict[str, int] = {}
    matched = 0
    left = 0
    best_start, best_length = 0, len(text) + 1

    for right, character in enumerate(text):
        if character in need:
            have[character] = have.get(character, 0) + 1
            if have[character] == need[character]:
                matched += 1

        # Shrink while the window is still valid: a valid window can only get
        # shorter by losing characters from the left, so record before evicting.
        while matched == len(need):
            if right - left + 1 < best_length:
                best_start, best_length = left, right - left + 1
            leaving = text[left]
            if leaving in need:
                have[leaving] -= 1
                if have[leaving] < need[leaving]:
                    matched -= 1
            left += 1

    return "" if best_length > len(text) else text[best_start:best_start + best_length]


print(min_window("ADOBECODEBANC", "ABC"))
print(repr(min_window("a", "aa")), repr(min_window("a", "a")), repr(min_window("ab", "b")))

BANC
'' 'a' 'b'

On "ADOBECODEBANC" the window becomes valid three separate times. The first valid window is "ADOBEC" at indices 0 to 5, length 6. It is recorded, then the leading A is evicted and the window is invalid again until the A at index 10 arrives. That second stretch shrinks all the way down to "CODEBA", length 6 — a tie, so nothing is recorded — before its C is evicted. The final C at index 12 makes it valid a last time, and shrinking from "ODEBANC" gives "EBANC" at length 5 and then "BANC" at length 4.

Note the have[leaving] < need[leaving] test on eviction. Dropping a B when the window holds two of them does not invalidate anything, so matched must only fall when the count actually drops below what is required.

Longest run with at most k distinct values

The same skeleton with a plain counter. The rule is len(counts) being at most k, and the one detail that catches people is that a key whose count reaches zero must be deleted, because len() counts keys, not non-zero keys.

def longest_at_most_k_distinct(values: list[int], k: int) -> int:
    """Length of the longest run containing at most k distinct values."""
    if k <= 0:
        return 0

    counts: dict[int, int] = {}
    left = 0
    best = 0

    for right, value in enumerate(values):
        counts[value] = counts.get(value, 0) + 1
        while len(counts) > k:
            leaving = values[left]
            counts[leaving] -= 1
            if counts[leaving] == 0:
                # A key left at zero would still be counted by len(counts).
                del counts[leaving]
            left += 1
        best = max(best, right - left + 1)

    return best


def window_travel(values: list[int], k: int) -> tuple[int, int, int]:
    """Return (best length, steps right took, steps left took)."""
    counts: dict[int, int] = {}
    left = 0
    best = 0
    right_steps = left_steps = 0

    for right, value in enumerate(values):
        right_steps += 1
        counts[value] = counts.get(value, 0) + 1
        while len(counts) > k:
            leaving = values[left]
            counts[leaving] -= 1
            if counts[leaving] == 0:
                del counts[leaving]
            left += 1
            left_steps += 1
        best = max(best, right - left + 1)

    return best, right_steps, left_steps


for sample, width in [([1, 2, 1, 3, 4], 2),
                      ([(index * index) % 13 for index in range(100_000)], 5)]:
    best, right_steps, left_steps = window_travel(sample, width)
    print(f"n={len(sample):>7,}  k={width}  best={best:>2}  right moved "
          f"{right_steps:>7,}  left moved {left_steps:>6,}  total "
          f"{right_steps + left_steps:>7,}  (2n = {2 * len(sample):,})")

print(longest_at_most_k_distinct([1, 2, 1, 3, 4], 2),
      longest_at_most_k_distinct([1, 1, 1], 1),
      longest_at_most_k_distinct([], 3))

n=      5  k=2  best= 3  right moved       5  left moved      3  total       8  (2n = 10)
n=100,000  k=5  best=10  right moved 100,000  left moved 99,992  total 199,992  (2n = 200,000)
3 3 0

collections.Counter will do the counting dict for you, but it does not delete keys that hit zero, so len() on a Counter after a decrement is not the distinct count. Either del the key yourself, as above, or track the distinct count in a separate integer.

This function is also the building block for the harder question "how many runs contain exactly k distinct values". Counting runs with exactly k distinct is counting runs with at most k, minus counting runs with at most k − 1 — the same window run twice, with a running total of window lengths instead of a maximum.

The precondition, and where sliding window breaks

Here is the failure everyone should see once. The problem: find the longest run whose sum is at most a given limit. The window version is four lines and it is correct on non-negative input.

def longest_at_most_sum(values: list[int], limit: int) -> int:
    """Longest run whose sum is at most limit. Correct only for non-negative values."""
    left = 0
    total = 0
    best = 0

    for right, value in enumerate(values):
        total += value
        while left <= right and total > limit:
            total -= values[left]
            left += 1
        best = max(best, right - left + 1)

    return best


def longest_at_most_sum_brute(values: list[int], limit: int) -> int:
    """Check every run. Slow, but right on any input."""
    best = 0
    for start in range(len(values)):
        running = 0
        for end in range(start, len(values)):
            running += values[end]
            if running <= limit:
                best = max(best, end - start + 1)
    return best


non_negative = [3, 1, 2, 4, 1]
with_a_negative = [2, 5, -5, 1]
print(longest_at_most_sum(non_negative, 6), longest_at_most_sum_brute(non_negative, 6))
print(longest_at_most_sum(with_a_negative, 3), longest_at_most_sum_brute(with_a_negative, 3))

agree = all(
    longest_at_most_sum(sample, 10) == longest_at_most_sum_brute(sample, 10)
    for sample in (
        [(index * 7 + offset * 5) % 9 for index in range(30)] for offset in range(200)
    )
)
print("non-negative samples agree:", agree)

3 3
2 4
non-negative samples agree: True

Two hundred non-negative inputs agree. [2, 5, -5, 1] with a limit of 3 does not: the window says 2, the truth is 4.

Trace it. At right = 1 the window is [2, 5] with a sum of 7, over the limit, so the shrink loop evicts the 2 (sum 5, still over) and then the 5 (sum 0), leaving left at 2 with an empty window. From there the best it can ever report is a run starting at index 2, and the answer — the whole array, which sums to exactly 3 — starts at index 0. That start was thrown away and left cannot go back.

The monotonicity precondition is what failed. With a negative in the array, removing a value from the left can increase the sum, so "invalid" no longer implies "invalid for every earlier left edge". There is no threshold to shrink towards, and the entire justification for a one-directional left pointer collapses. No exception, no warning, just a smaller number than the right one.

The repair is not a patched window, it is a different algorithm. Write prefix[i] for the sum of the first i values; then the sum of a run from i to j is prefix[j + 1] - prefix[i], and the question becomes a search over prefix values rather than a walk over window edges. Prefix sums covers that shift. The related question "is there a run summing to exactly S", which sliding windows also cannot answer once negatives appear, is solved in O(n) by storing every prefix sum in a hash table and looking up prefix - S at each step.

The same caution applies whenever the rule is not monotone under shrinking. "Longest run whose product is at most P" breaks the moment a zero or a value below 1 appears, for exactly the same reason.

Complexity

Fixed window: O(n) time, O(1) space. The first window costs k reads. Each of the remaining n - k steps costs exactly two reads and one comparison. Total: k + 2(n - k), which is at most 2n, so O(n). The naive version is (n - k + 1) * k, which is O(n · k) — and when k is proportional to n, that is O(n²).

Variable window: O(n) time, amortised. This is the argument to be able to give, because the code contains a while loop inside a for loop and that shape is quadratic in most other contexts.

Count the two edges separately instead of counting loop iterations:

• right advances exactly once per outer iteration, so it takes exactly n steps over the whole run.
• left starts at 0, only ever increases, and never passes n. So left takes at most n steps in total, across the entire run — not per outer iteration, in total.

Each step of either edge does a constant amount of work: one dict update, one comparison, one arithmetic operation. So the total work is bounded by n + n = 2n constant-cost steps, which is O(n).

One caveat worth naming rather than glossing over. A dict update is O(1) on average, not guaranteed — a set of keys that all hash to the same bucket drags a single lookup out to O(n). So the counting windows are O(n) expected, not O(n) come what may. The sum-based windows hold no dict and carry no such caveat.

The reason the nested loop does not multiply is that the two loops share one budget. A nested loop is quadratic when the inner count is independent of the outer loop's progress — an inner loop that runs n times for each of n outer iterations. Here every inner iteration permanently consumes one of the n moves left will ever make. A single outer iteration can trigger a long shrink, but that shrink is stolen from the budget of every later iteration. The measurement above says it plainly: on 100,000 elements, right moved 100,000 times and left moved 99,992 times, for 199,992 total moves against a ceiling of 200,000.

Space. O(1) for the sum-based windows: two indices and a running total. The counting windows hold a dict, bounded by the number of distinct values that can be inside a valid window — at most k + 1 keys for the at-most-k-distinct version, at most one key per distinct character for longest_unique (128 for plain ASCII text, so effectively constant), and at most one key per distinct character of the target for min_window.

Against the brute force, on a list of n items:

The left column is n(n + 1) / 2, the number of contiguous runs in a list of n items. Ten times the data costs a hundred times the work there and ten times the work on the right.

When to use it, and when not to

Use it when three things are true: the answer is a contiguous run, the property you are testing can be updated in constant time when one element joins and one leaves, and shrinking from the left can restore validity. Sums, counts, character frequencies and "at most k of something" all satisfy the second condition. Maximums do not, which is the one common exception worth knowing — when the largest value in the window is the one leaving, you cannot recover the new largest in O(1) without extra structure. That problem, sliding window maximum, is solved with a monotonic collections.deque holding indices in decreasing value order, and it is still O(n) overall because each index is pushed and popped once.

Do not use it when the answer is not contiguous. "Longest increasing subsequence" and "longest common subsequence" allow gaps, and no window can express a gap. Those are dynamic programming problems.

Do not use it when the answer is a pair of positions rather than a range. That is the two pointers technique, a close relative where the two indices usually move towards each other rather than both rightwards, and where what sits between them is irrelevant.

Do not use it when the rule is not monotone under shrinking, as shown above. Sums with negatives, products with zeros or fractions, and any rule where removing an element can make things worse are all disqualified.

Do not use it for arbitrary range queries either. If the question is "the sum of indices 300 to 700" asked a thousand times over a fixed array, a window has nothing to slide along; build a prefix-sum array once and answer each query in O(1).

Where it shows up in the real world

TCP flow control. The receiver advertises a window size, and the sender may have at most that many unacknowledged bytes in flight. As acknowledgements arrive the window's left edge advances and new bytes become sendable on the right. It is the same two-edge structure, running on every connection your machine has open.

DEFLATE, the algorithm behind gzip, zlib and PNG. Its LZ77 stage encodes repeated data as back-references into a sliding window of the previous 32 KB of output. Data older than 32 KB has fallen out of the window and can no longer be referenced, which is precisely the trade that keeps the compressor's memory constant regardless of file size.

Rolling hashes. Rabin-Karp slides a fixed-width window over the text and updates the hash by removing the leaving character's contribution and adding the entering one's — the add-one-remove-one update on a hash instead of a sum. Content-defined chunking in backup and deduplication systems uses the same rolling window to decide where to cut a file.

Stream processing. Apache Flink and Kafka Streams both expose windowing as a first-class operator: tumbling windows that never overlap, and sliding or hopping windows that advance by less than their width. The aggregation kept per window is maintained incrementally as records enter and expire.

API rate limiting. The sliding-window-counter algorithm approximates a rolling limit by blending the current fixed window's count with a weighted share of the previous window's, which gives per-client memory of two integers instead of one timestamp per request. Cloudflare has published this approach for its rate limiter.

Signal processing. The short-time Fourier transform behind every spectrogram slides a fixed-width window along a waveform, usually with overlap, and transforms each position independently.

Common mistakes

Recomputing the property inside the loop. Writing sum(values[left:right + 1]) or len(set(text[left:right + 1])) inside the loop is the single most common way to write a sliding window that is secretly O(n²). The whole technique is the incremental update; if you recompute, you have kept the code and thrown away the algorithm.

Using if instead of while to shrink. One eviction is often not enough. On [1, 2, 1, 3] with k of 2, when the 3 arrives the window holds three distinct values; evicting index 0 removes a 1 but another 1 remains at index 2, so the count is still 3 and a second eviction is required.

Letting the left edge move backwards. The "abba" bug above. Any expression that assigns left a value without taking a maximum against its current value should be treated as suspect until you have proved the new value cannot be smaller.

Leaving zero-count keys in the dict. counts[value] -= 1 without the del when it reaches zero means len(counts) keeps counting a value that is no longer in the window, and the window never shrinks enough.

Recording the answer in the wrong place. For a longest-window problem, record after the shrink loop, when the window is valid. For a shortest-window problem, record inside the shrink loop, before evicting. Swapping them gives answers that are plausible and wrong.

Mixing up the two length conventions. With both ends inclusive the length is right - left + 1. With right exclusive it is right - left. Pick one and use it in every line, including the initial best.

Assuming a window applies because the problem mentions subarrays. Check the monotonicity precondition first. If shrinking cannot repair an invalid window, no amount of careful coding will save it.

Practice

1. Given a list of numbers and a width k, return the largest average of any k consecutive values.
2. Given a string, find the length of the longest substring containing at most two distinct characters.
3. Given a list of non-negative integers and a target, find the length of the shortest run whose sum is at least the target, returning 0 if none exists.
4. Given two strings, report every index in the first where an anagram of the second begins, using a fixed-width window of character counts.
5. Given a list and a width k, return the maximum of every window of that width, keeping the whole thing O(n) with a collections.deque of indices held in decreasing value order.

Summary

A sliding window replaces recomputation with repair. Fixed-size windows patch a running total with one addition and one subtraction; variable-size windows grow on the right and shrink on the left until the rule holds again. The linear bound comes from counting edge movements rather than loop iterations — each of the two edges makes at most n forward moves over the whole run, so the nested while costs 2n steps in total and not n² — and the correctness comes from a precondition that is easy to state and easy to forget: shrinking from the left must be able to restore validity. Verify that condition before you write the loop, because when it fails the code still runs.

Keep reading

• The Two Pointers Technique — the sibling pattern, for when the answer is a pair of positions rather than a run.
• Prefix Sums — what to reach for when negatives break the window, and how to answer range queries in O(1).
• Hash Tables — why the counting dicts above are O(1) per update on average, and the prefix-sum lookup trick for negatives.
• Rabin-Karp — a rolling hash is the add-one-remove-one update applied to a hash function.
• Big O Notation — the amortised counting argument used here, from first principles.