Purely Functional Sliding Window Aggregation Algorithm

Suppose we have a list of items of length \(n\), and we want to consider windows (i.e. contiguous subsequences) of width \(w\) within the list. ⊕ A list of numbers, with contiguous size-3 windows highlighted We can compute the sum of each window by brute force in \(O(nw)\) time, by simply generating the list of all the windows and then summing each. But, of course, we can do better: keep track of the sum of the current window; every time we slide the window one element to the right we can add the new element that enters the window on the right and subtract the element that falls of the window to the left. Using this “sliding window” technique, we can compute the sum of every window in only \(O(n)\) total time instead of \(O(nw)\). How about finding the maximum of every window? Of course the brute force \(O(nw)\) algorithm still works, but doing it in only \(O(n)\) is considerably trickier! We can’t use the same trick as we did for sums since there’s no way to “subtract” the elem ... Read full article.