Stream: Minimum element in sliding window

You are given an array of size n (may be a stream also). You have a sliding window of size k. The window first boxes the first k elements of the array and slides slowly over the array by shifting its position 1 element each time. At each position of the array, you need to find the minimum element in the sliding window. i.e. you need to give the minimum of 0 to k-1 elements, then 1 to k elements, 2 to k+1 elements etc. So if your array's size is n, you have to give me n-k+1 minimum values.
E.g. Assume that the array is 5,1,3,2,6,8,4,6, and the window size is 3
You should give me 1,1,2,2,4,4. How will you give it?


Approach:
http://www.tiac.net/~cri/2001/slidingmin.html



If you are lazy enough to go to the link, am pasting the contents over here:

The sliding window minimum (maximum) problem runs as follows:

We are given a vector V of numeric values of length n and a window size, k. Produce a vector R containing the minimum seen in a window as it slides over the vector V. This formulation can be interpreted in one of two ways, depending on whether the we start with a full window or with a partial window. Here is an example:

    

    k = 3, V = {4,3,2,1,5,7,6,8,9,...}

In the full window case we define R[i] as the minimum value of V[j] for j=i,...,i+k-1. For our example we get

    R = {2,1,1,1,5,6,6,...}

In the partial window case we define R[i] as the minimum value of V[j] for j = max(0,i-k+1),...,i. For our example we get

    R = {4,3,2,1,1,1,5,6,6,...}

The partial window version has an additional k-1 values at the beginning of R; other than that they are identical.

The ascending minima algorithm

The algorithm presented here is the ascending minima algorithm; it requires O(n) time and O(k) space. The general idea is to locate the minimum in the window, then the minimum in the remainder of the window, and so. Values between the ascending minima can be ignored.

More formally, let W be a vector of values of length k. Define the sequence of ascending mimima, A, as follows:

Let A[0] be the minimum value in W and for j>0 let A[j] be the minimum value in W with index greater than the index of A[j-1]. (If two locations have the same minimum value take the later one.) Example:

W = 5,2,8,6,4,7

A = 2,4,7

Evidently the length of A is 1 if the minimum in W is the last element in W and k if W is monotonic increasing.

Now suppose that we have a window W on V and that we know the ascending minima vector A. Consider what happens when we move the window one location. We add one element at the end of the window and remove one element from the beginning of the window. Let x be the newly added element. Then A can be updated by

removing all elements of A greater than or equal to x,

appending x to A, and

removing the initial element of A if it is being removed from the window.

We do not need to record the window; all we need is the ascending minima sequence. However it is necessary to record when an entry in the sequence will be deleted from the window. For this reason it is useful if the elements of A have two fields, the first being a value from V, i.e., V[i] for some i, and the second being the index when the entry will disappear from the window. This happens k entries later.

Since the length of A is bounded and since A is a queue, it is natural to store it in a ring buffer.

Steps (b) and (c) are straightforward without significant alternatives. In step (a) we need to locate the last value in A that is less than the newly added x. At first sight it might seem that a binary search of A would be optimal. This is not the case; the optimal search is from back to front in a simple loop.

The proof is simple enough; the linear search loop deletes elements one by one with an O(1) time cost for each deletion. On average the number of deletions from A is the same as the number of additions. The upshot is that the average time cost of moving the window one location is O(1).

Alternatives

There are two obvious alternatives to the ascending minima algorithm. The first is a simple "track the minimum" scheme. The second is to use a heap.

Track the minimum

In the first the plan is to locate the minimum in the window. When the window moves there are three possible actions. These are:

If the current minimum is deleted we scan the window to find the new minimum.

If the newly added value is less than or equal to the current minimum, mark it as the current minimum.

Otherwise do nothing.

Evidently the expected cost depends on how often we have to rescan the window. One might argue that the average cost is O(1) since on average the minimum will be located at the midpoint of window when we scan. The idea is that the frequency of scans is 2/k with a cost per scan of O(k*2/k) = O(1). A more legitimate form of this argument is to assume that all locations are equally likely. In such case the cost is O(1+1/2+...+1/k) = O(log k).

There is a catch. If the wavelength of the data is longer than the window, i.e., if there are stretches longer than the window of mostly increasing data and of mostly decreasing data, the cost will be O(k). The reason is that in increasing stretches the next minimum is regularly very close to the beginning of the window, so the increasing stretches are O(k). Of course the decreasing stretches are O(1) but the average is O(k).

Use a heap

The second alternative is to put the window values in a heap. There will need to be a mapping from window position to location within the heap. This can be handled with a linked list; the mechanics are O(1). When the window is updated, the deleted item is removed from the heap and is replaced with the added item, which is then sifted up or down as needed.

If the distribution of the values being inserted is random and unbiased, the average cost of updating the heap is O(1). Again there is a catch, and it is the same catch. When the data is mostly increasing the root is regularly deleted and the cost of updating the heap is O(log k).

Conclusion

The upshot is that the time costs are:

Algorithm Random   Mostly increasing 

Ascending minima: O(1) O(1)

Use a heap: O(1) O(log k)

Track the minimum:  O(log k) O(k)

The "track the minimum" algorithm has the advantages of being simple and cache friendly. However its performance can be very bad for large k. Using a heap is a viable alternative; it is a familiar data structure and the performance is not horrid. However using a heap is more complicated than the "ascending minima" algorithm and its performance is worse.

In many applications it probably won't matter which algorithm is used - the cost for computing the minimum on a sliding window will be small compared to other costs. None-the-less, it is as easy to use the better algorithm as the worse, and sometimes the costs do matter.