AI Hints
Home›DSA in Python Tutorial›Windows and Prefixes
DSA in Python · Lesson 25 of 132

Sliding Window

A moving range.

⏱ 2 min read▶ Video at 28:40🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Imagine a window that slides along an array, showing a few items at a time. As it moves one step, one item enters on the right, and one item leaves on the left. You don't need to recount everything. You just adjust. That's the sliding window technique.

Sliding Window
From the video: Sliding Window
  • A window slides along
  • One item in, one item out
  • Adjust, don't recount

Best three day total

Here are daily sales, and we want the best total over any three days in a row. We add up the first three days. Then, for each step, we add the day entering the window, and subtract the day leaving it. Run it. The best three days total twenty one. Each step is O of one, so the whole scan is O of N, instead of re adding every window.

window.pypython
def best_window(sales, k):
    window = sum(sales[:k])
    best = window
    for i in range(k, len(sales)):
        window += sales[i] - sales[i - k]
        best = max(best, window)
    return best

sales = [4, 2, 7, 1, 8, 3, 10, 2]
print(best_window(sales, 3))
Output
21

Fixed and growing windows

Some windows have a fixed size, like three days. Others grow and shrink. The window grows on the right while things are fine, and shrinks from the left when a rule is broken. The next lesson uses that kind. Both are O of N, because each item enters and leaves the window at most once.

keyvalue
Fixed windowsize k, slide by one
Growing windowexpand right
Shrinkingmove left when needed
CostO(n), each item in and out once

Summary

A sliding window adds what enters, and removes what leaves, so each step is O of one. Next, a famous growing window problem.

Key takeaways
  • Add the new item
  • Remove the old item
  • O(n)
Next up: Practice: Longest Substring — no repeated characters