Card 08/ 08
Recap: Sliding Window
A fixed window slides one step at a time; a variable window grows until the rule breaks and shrinks until it holds again.
A sliding window keeps a running answer for a contiguous run and updates it as the run moves, so each element enters once and leaves at most once and the pass is O(n). The question decides which window to use: a fixed length takes a fixed window, and a rule on the run's contents takes a variable one. Set side by side:
| Window | Cue | When start moves | Invariant | Cost |
|---|---|---|---|---|
| Fixed | Every run of exactly k elements | Every step, once the window holds k | The window holds the last k elements | O(n) time, O(1) per step |
| Variable | The longest or shortest run that satisfies a rule | While the rule is broken, for the longest; while it holds, for the shortest | After shrinking, the window satisfies the rule | O(n) time, O(1) or O(k) extra space |
A map inside the window holds what the rule needs: the last position of each item, so start can jump past a repeat with max(start, last + 1), or a count of each item with a second number for how many are present, so validity is one comparison. A variable window needs a rule that moves one way as the window grows. A sum over values that can be negative breaks it, and the shortest run is missed; check every run, or use prefix sums, instead.
← → move through sections and cards