Sliding window over a list¶

~20 min · prerequisite: Two pointers on sorted data

What you will be able to do¶

Keep a window, which is a contiguous run of a list, and update its total as one end moves.
Find the longest window that satisfies a rule, such as a sum limit or a count of distinct values.
Explain why the whole scan takes about 2n window updates, and state the condition that makes this work.

The idea¶

A subarray is a run of neighbouring values in a list, such as the values at positions 2 to 5. A sliding window is a subarray whose two ends only move forward. The right end moves one step at a time to take in a new value. The left end moves when the window breaks the rule and must shrink.

Consider the longest subarray whose sum is at most limit. Try every start and every end, and you check about n² subarrays. The window method does better. Move the right end across the list, adding each value to a running total. Whenever the total is above the limit, move the left end forward and subtract the value it leaves behind. After each step, the window is the longest valid window that ends at the right end, and you record its length.

The method is correct only for non-negative values. With non-negative values, adding a value never lowers a sum, and removing one never raises it. So the valid left ends for each right end start at some point and only move forward as the right end moves. Negative values break this, and the next section shows how.

The cost is easy to count. The right end moves n times in total, and the left end never moves backward, so it moves at most n times. Each move changes the total by one value in constant time. That makes at most 2n updates, which is O(n).

A second rule works the same way. To keep at most k distinct values, store how many copies of each value are in the window. Shrink the window while more than k distinct values are present. The count of distinct values is the number of keys with a count above zero, so a key whose count drops to zero must be removed.

Worked example¶

This function returns the length of the longest subarray with sum at most limit. All values must be non-negative.

def longest_at_most(values, limit):
    best = 0
    total = 0
    l = 0
    for r, x in enumerate(values):
        total += x
        while total > limit:
            total -= values[l]
            l += 1
        best = max(best, r - l + 1)
    return best


assert longest_at_most([1, 2, 3, 4, 5], 9) == 3

Line by line, this is what Python does with [1, 2, 3, 4, 5] and limit = 9:

enumerate(values) gives each position r with its value x, so r is the right end.
The right end takes in 1, 2 and 3. The total is 6, which is within the limit.
It takes in 4, so the total is 10. The while loop runs: it removes values[0], which is 1, so the total is 9 and the left end is at position 1.
The window is [2, 3, 4], with length r - l + 1 = 3 - 1 + 1 = 3. The best value is 3.
The right end takes in 5, the total is 14, and the loop removes 2 and 3 to reach 9. The window is [4, 5], which is shorter than the best.
The function returns 3.

Try it¶

The first block compares the function with a brute-force search on random non-negative lists. The second block finds the longest window with at most k distinct values, using counts.

import random


def longest_at_most(values, limit):
    best = 0
    total = 0
    l = 0
    for r, x in enumerate(values):
        total += x
        while total > limit:
            total -= values[l]
            l += 1
        best = max(best, r - l + 1)
    return best


def brute(values, limit):
    n = len(values)
    lengths = [j - i for i in range(n) for j in range(i + 1, n + 1) if sum(values[i:j]) <= limit]
    return max(lengths, default=0)


for _ in range(2000):
    values = [random.randint(0, 6) for _ in range(random.randint(0, 8))]
    limit = random.randint(0, 12)
    assert longest_at_most(values, limit) == brute(values, limit)

def longest_k_distinct(values, k):
    counts = {}
    best = 0
    l = 0
    for r, x in enumerate(values):
        counts[x] = counts.get(x, 0) + 1
        while len(counts) > k:
            counts[values[l]] -= 1
            if counts[values[l]] == 0:
                del counts[values[l]]
            l += 1
        best = max(best, r - l + 1)
    return best


assert longest_k_distinct([1, 2, 1, 2, 3], 2) == 4
assert longest_k_distinct([5, 5, 5], 1) == 3
assert longest_k_distinct([], 3) == 0

Common mistakes¶

Using negative values. The shrink rule assumes that removing a value never raises the sum. With [1, -3] and limit 0, the whole list has sum -2, which is valid, but the function returns a shorter answer:
```
assert longest_at_most([1, -3], 0) == 2
```
```
AssertionError
```
When negative values are possible, use prefix sums and a different method.
Leaving zero counts in the dictionary. If a key whose count reached 0 is not deleted, len(counts) counts a value that is no longer in the window. No error appears, but the window shrinks too far. Delete the key as longest_k_distinct does.
Measuring the length without the + 1. The length of the window from position l to r is r - l + 1. Writing r - l loses one value, and the answer is too small by one. No error appears.
Moving the left end past the right end. If the limit is negative, even an empty window fails the test, and the loop keeps reading past the window. The code below shows this, because values[1] does not exist:
```
values = [1]
limit = -1
total = 0
l = 0
for r, x in enumerate(values):
    total += x
    while total > limit:
        total -= values[l]
        l += 1
```
```
IndexError: list index out of range
```
Check the constraints of the problem before you write the loop.

Practice¶

Easy: write longest_run(values) that returns the length of the longest run of equal neighbouring values. Check longest_run([1, 1, 2, 2, 2, 3]) is 3.
Easy: check that longest_at_most([4, 1, 1, 1], 3) is 3, using the function from the worked example.
Medium: write longest_one_zero(values) that returns the length of the longest window with at most one 0. Check longest_one_zero([1, 0, 1, 1, 0, 1]) is 4.
Medium: write min_len_at_least(values, target) that returns the length of the shortest window with sum at least target, for non-negative values, and 0 if no window reaches it. Check min_len_at_least([2, 3, 1, 2, 4, 3], 7) is 2.
Stretch: write count_at_most(values, limit) that counts all subarrays with sum at most limit, for non-negative values. Check count_at_most([1, 2, 3, 4], 5) is 6.

Solution

```python def longest_run(values): best = 0 run = 0 for i, x in enumerate(values): run = run + 1 if i > 0 and x == values[i - 1] else 1 best = max(best, run) return best

assert longest_run([1, 1, 2, 2, 2, 3]) == 3 ```

```python def longest_at_most(values, limit): best = 0 total = 0 l = 0 for r, x in enumerate(values): total += x while total > limit: total -= values[l] l += 1 best = max(best, r - l + 1) return best

assert longest_at_most([4, 1, 1, 1], 3) == 3 ```

The window [1, 1, 1] has sum 3. Adding the 4 breaks the limit.

```python def longest_one_zero(values): l = 0 zeros = 0 best = 0 for r, x in enumerate(values): if x == 0: zeros += 1 while zeros > 1: if values[l] == 0: zeros -= 1 l += 1 best = max(best, r - l + 1) return best

assert longest_one_zero([1, 0, 1, 1, 0, 1]) == 4 ```

```python def min_len_at_least(values, target): l = 0 total = 0 best = 0 for r, x in enumerate(values): total += x while total - values[l] >= target and l < r: total -= values[l] l += 1 if total >= target and (best == 0 or r - l + 1 < best): best = r - l + 1 return best

assert min_len_at_least([2, 3, 1, 2, 4, 3], 7) == 2 ```

The shrink step keeps the window as short as possible while its sum stays at least target. The l < r test stops the shrink at a single value.

```python def count_at_most(values, limit): l = 0 total = 0 count = 0 for r, x in enumerate(values): total += x while total > limit: total -= values[l] l += 1 count += r - l + 1 return count

assert count_at_most([1, 2, 3, 4], 5) == 6 ```

For each right end r, every start from l to r gives a valid window, so the function adds r - l + 1.

Recap¶

A sliding window keeps a running total or count, and moves its two ends forward only.
Each end moves at most n times, so the scan costs O(n) window updates.
The sum rule needs non-negative values, and a dictionary of counts must delete keys that reach zero.