PART 4 · DSA AND COMPLEXITY · CHAPTER 20

Sliding windows of variable size

FreeLesson 45 of 78

A variable window grows on the right until a rule breaks, then shrinks from the left until the rule holds again. Each item enters and leaves once, so it is O(n).

LONGEST SUBSTRING WITHOUT REPEATING CHARACTERSPYTHON 3.12

def longest_unique(s):
    last = {}                       # char -> last index seen
    start = best = 0
    for i, ch in enumerate(s):
        if ch in last and last[ch] >= start:
            start = last[ch] + 1     # shrink past the repeat
        last[ch] = i
        best = max(best, i - start + 1)
    return best

print([longest_unique(s) for s in ["abcabcbb", "pwwkew", ""]])

Output

[3, 3, 0]

SHORTEST RUN OF DAYS REACHING A TARGETPYTHON 3.12

def shortest_with_sum(nums, target):
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x                       # grow
        while total >= target:           # rule met: try to shrink
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

print(shortest_with_sum([2, 3, 1, 2, 4, 3], 7))

Output

Works because all values are positive: growing the window only increases the total, shrinking only decreases it. With negative numbers this breaks; use the prefix-sum map from page 46 instead.

DE FLAVOUR: BUSIEST 30-MINUTE WINDOW OF EVENTSPYTHON 3.12

from collections import deque
from datetime import datetime, timedelta

times = ["10:00", "10:02", "10:05", "10:20", "10:22", "10:40",
         "11:00", "11:10", "11:15", "12:00"]
ts = [datetime.strptime(t, "%H:%M") for t in times]

window, peak = deque(), (0, None)
for t in ts:                                   # already sorted by time
    window.append(t)
    while window[0] <= t - timedelta(minutes=30):
        window.popleft()                       # older than 30 minutes
    if len(window) > peak[0]:
        peak = (len(window), t.strftime("%H:%M"))
print("busiest 30-minute window:", peak[0], "events, ending", peak[1])

Output

busiest 30-minute window: 5 events, ending 10:22

Fixed-size window (P5)	Variable-size window (this page)
Size Always k items or k days	Grows and shrinks with a rule
Move Add one on the right, drop one on the left	Add on the right; drop from the left while the rule is broken
State Running total, or a deque of the last k	A dict of counts or last positions, or a running total
Typical question Rolling 7-day revenue, moving average	Longest run with no repeats, shortest run reaching a target

Practice before you move on

Find the longest run of consecutive rows in orders.csv with no repeated customer_id.
Change the 30 minute window in the events example to 15 minutes and compare the result.