The question this module answers: what's the best contiguous range? There are n(n + 1)/2 contiguous ranges in an array of n values. Checking each one from scratch is O(n²) or O(n³). A sliding window visits them in an order where each range differs from the last by one element entering or leaving, so its summary (a sum, a count, a set) updates in O(1). Every element enters once and leaves once: O(n).
ML context. Windows are everywhere in ML code:
- Rolling averages of training loss, latency or a production metric.
- n-grams: every run of n consecutive tokens.
- Time-series features: counts and sums over the last hour, the last 1,000 events.
- Context windows: which tokens a model can see, and chunking long documents with overlap.
1. The problem: recomputing every range
Task: the largest sum of any 3 consecutive values.
Neighbouring windows share k − 1 values, yet each sum starts from zero: O(n·k).