Sliding Window

A sliding window keeps a running answer for a contiguous run of an array as the run moves along it: a fixed window adds the element entering and removes the one leaving, and a variable window grows on the right and shrinks from the left only while its rule is broken. It matters because every element then enters and leaves once, so a question about all the runs of an array costs O(n) instead of O(n²). The topic opens on the longest run of daily costs within a budget, finds the longest stretch of a playlist with no artist twice, and gives the variable window template in Python, Java and TypeScript. It slides a fixed window over a shop's hourly footfall, finds the shortest stretch of a timetable served by every route, shows the shortest run missed when negative numbers enter a sum window, and ends with an exercise on the climbs along a cycling route.