Sliding window: fixed size
A window is a contiguous slice of a list. Many problems ask about the best window: highest 3-day sales total, longest clean substring, shortest chunk with a big enough sum.
The naive way recomputes each window from scratch: n windows × k elements = O(n·k). The sliding window trick: when the window slides one step right, only two elements change. Add the one entering, subtract the one leaving. Each slide becomes O(1) and the whole scan is O(n).
window += nums[i] - nums[i - k]
That one line replaces re-summing k elements.
Code exercise · python
Run this. best_window finds the largest sum of any 3 consecutive days. Note the update line: one add, one subtract per slide.
Variable-size windows
Harder problems do not fix the window size, they fix a condition: longest substring with no repeated character, shortest run summing to ≥ target. The pattern:
rightmarches forward one step per loop, growing the window.- After each growth, a
whileloop shrinks fromleftas long as the window is invalid (or, for shortest-window problems, as long as it is still valid, recording answers as you shrink). - Track the best window seen.
It looks like nested loops, but it is O(n): left only ever moves forward, so each element enters the window once and leaves at most once. This is the single most common pattern in string interview problems.
Code exercise · python
Run this. The classic: longest substring without repeating characters. The while loop evicts from the left until the incoming character is no longer a repeat.
Code exercise · python
Your turn, the mirror problem: SHORTEST contiguous run whose sum is at least target. Grow with right, and while the sum is big enough, record the length and shrink from the left. Return 0 if no run works.
Quiz
longest_unique has a while loop inside a for loop. Why is it still O(n) rather than O(n²)?
Problem
A list has 10 elements. How many different windows of size 3 does it contain?