Sliding window technique explained with Python

A sliding window keeps a running total of k neighboring items and moves one step at a time: add the item coming in, subtract the one going out. That finds the best sum of k consecutive days in O(n) instead of O(n·k).

The code

Here are ten days of sales in dollars. Which 7 days in a row sold the most?

def best_run(sales, k):
    if len(sales) < k:
        return None
    total = sum(sales[:k])          # the first window
    best = total
    best_start = 0
    for right in range(k, len(sales)):
        total += sales[right] - sales[right - k]   # add new, drop old
        if total > best:
            best = total
            best_start = right - k + 1
    return best, best_start

sales = [120, 80, 150, 60, 200, 90, 170, 40, 110, 210]
print(best_run(sales, 7))   # (880, 3)
print(best_run(sales, 3))   # (460, 4)
print(best_run(sales, 11))  # None

Output:

(880, 3)
(460, 4)
None

The best 7-day run starts at index 3 and sold $880.

How it works

• First window: sum(sales[:k]) adds the first k days once.
• Slide: each step, right is the new day entering the window and right - k is the day leaving it. One addition and one subtraction update the total.
• Track the best: whenever the total beats best, remember it and where the window starts (right - k + 1).

Every day is added once and subtracted once, so the whole loop is O(n). It uses O(1) extra memory.

Because the window size never changes, this is called a fixed-size window. If the size is the question, such as the shortest run reaching a target, you need a window that grows and shrinks instead.

Common mistake

Recomputing the sum for every window. Writing sum(sales[i:i + k]) inside the loop works, but it costs O(n·k) and gets slow on long lists. Update the running total instead.

Not checking the list length. If sales has fewer than k items, the slice just takes what is there and no error is raised, so you get a wrong answer. Check len(sales) < k first and return None.

Takeaway

A fixed sliding window turns "best sum of k in a row" into one pass: add the new item, drop the old one, and keep the best total.