Computing a moving maximum

Question

Possible Duplicate:
Find the min number in all contiguous subarrays of size l of a array of size n

I have a (large) array of numeric data (size N) and would like to compute an array of running maximums with a fixed window size w.

More directly, I can define a new array out[k-w+1] = max{data[k-w+1,...,k]} for k >= w-1 (this assumes 0-based arrays, as in C++).

Is there a better way to do this than N log(w)?

[I'm hoping there should be a linear one in N without dependence on w, like for moving average, but cannot find it. For N log(w) I think there is a way to manage with a sorted data structure which will do insert(), delete() and extract_max() altogether in log(w) or less on a structure of size w -- like a sorted binary tree, for example].

Thank you very much.

score 13 · Accepted Answer · edited May 23 '17 at 12:09

There is indeed an algorithm that can do this in O(N) time with no dependence on the window size w. The idea is to use a clever data structure that supports the following operations:

Enqueue, which adds a new element to the structure,
Dequeue, which removes the oldest element from the structure, and
Find-max, which returns (but does not remove) the minimum element from the structure.

This is essentially a queue data structure that supports access (but not removal) of the maximum element. Amazingly, as seen in this earlier question, it is possible to implement this data structure such that each of these operations runs in amortized O(1) time. As a result, if you use this structure to enqueue w elements, then continuously dequeue and enqueue another element into the structure while calling find-max as needed, it will take only O(n + Q) time, where Q is the number of queries you make. If you only care about the minimum of each window once, this ends up being O(n), with no dependence on the window size.

Hope this helps!

So good I had to up-vote both this answer and the answer you referenced! — Andy, Jan 18 '12 at 05:31
I have to comment here that the two-stack queue implementation isn't necessarily the best one. I've tried it, for a REAL-TIME application, and the result was catastrophic... Depending on the application, one might also try the deque (double-ended queue) structure, which will also give O(N) result overall, but not necessarily amortized O(1) for dequeue operation. I did a circular deque implemented on an array and it worked well. Check out this question as well: https://stackoverflow.com/questions/12329073/find-the-min-number-in-all-contiguous-subarrays-of-size-l-of-a-array-of-size-n. — Alan Wang, Sep 18 '17 at 00:41

score 1 · Answer 2 · edited Sep 24 '12 at 23:25

I'll demonstrate how to do it with the list:

L = [21, 17, 16, 7, 3, 9, 11, 18, 19, 5, 10, 23, 20, 15, 4, 14, 1, 2, 22, 13, 8, 12, 6]

with length N=23 and W = 4.

Make two new copies of your list:

L1 = [21, 17, 16, 7, 3, 9, 11, 18, 19, 5, 10, 23, 20, 15, 4, 14, 1, 2, 22, 13, 8, 12, 6]
L2 = [21, 17, 16, 7, 3, 9, 11, 18, 19, 5, 10, 23, 20, 15, 4, 14, 1, 2, 22, 13, 8, 12, 6]

Loop from i=0 to N-1. If i is not divisible by W, then replace L1[i] with max(L1[i],L1[i-1]).

L1 = [21, 21, 21, 21, | 3, 9, 11, 18, | 19, 19, 19, 23 | 20, 20, 20, 20 | 1, 2, 22, 22 | 8, 12, 12]

Loop from i=N-2 to0. If i+1 is not divisible by W, then replace L2[i] with max(L2[i], L2[i+1]).

L2 = [21, 17, 16, 7 | 18, 18, 18, 18 | 23, 23, 23, 23 | 20, 15, 14, 14 | 22, 22, 22, 13 | 12, 12, 6]

Make a list L3 of length N + 1 - W, so that L3[i] = max(L2[i], L1[i + W - 1])

L3 = [21, 17, 16, 11 | 18, 19, 19, 19 | 23, 23, 23, 23 | 20, 15, 14, 22 | 22, 22, 22, 13]

Then this list L3 is the moving maxima you seek, L2[i] is the maximum of the range between i and the next vertical line, while l1[i + W - 1] is the maximum of the range between the vertical line and i + W - 1.

Computing a moving maximum

2 Answers2

Linked