Sliding window

Many questions ask about a run of neighbouring values: the best stretch of a given length, or the longest stretch that meets a rule. A sliding window answers them by updating the run one value at a time, instead of starting again for each position.

A window of fixed size

Take the largest sum of k neighbouring values. Adding up each window from scratch costs k steps per window, which is O(n × k) in total. But two neighbouring windows share all but two values. Moving one place right adds the value that comes in and takes away the value that leaves.

def best_window(a, k):
    s = sum(a[:k])
    best = s
    for r in range(k, len(a)):
        s += a[r] - a[r - k]     # one in on the right, one out on the left
        best = max(best, s)
    return best

A window that grows and shrinks

Step through the second version: the longest run whose sum is at most a limit. Now the window has no fixed size. The right end hi moves one place each pass. The left end lo moves only when the window breaks the rule.

def longest_within(a, limit):      # all values positive
    lo = 0
    s = 0
    best = 0
    for hi in range(len(a)):
        s += a[hi]
        while s > limit:              # shrink until valid again
            s -= a[lo]
            lo += 1
        best = max(best, hi - lo + 1)
    return best

Why is that true? Suppose a longer valid window ended at hi; it would start before lo. But lo only moved past a position when the window starting there was over the limit. With positive values, adding more values on the right only makes the sum bigger, so that window is still over the limit now. So no valid window starts before lo.

Why it is O(n)

There is a loop inside a loop, so it looks like O(n²), n times n steps. Count moves instead of passes. hi moves right n times. lo also only moves right, and never past hi + 1, so it moves at most n times in total, across all passes. That is at most 2n moves: O(n). Counting the total over the whole run like this is the amortised idea from BIGO-7.

What the window remembers

The window needs a summary that can be updated in O(1) when one value enters or leaves:

• a running sum, for sum rules;
• a dictionary of counts, for rules about repeats or distinct values;
• a deque of candidates, for the largest value in each window (STAQ, the monotonic queue).

For “no repeated character”, keep a dictionary from each character to how many times it is in the window, or to the last index where you saw it. That is the practice problem.

Now try ARRS-P2, The longest run of different codes.