This is an original article that has been replaced. It has been retained for historical reasons.
The sliding window minimum (maximum) problem runs as follows:
Suppose that we are given a vector v of numeric values of length n and we want to produce a vector r of length n-k such that for r[i], i=0,...,n-k-1, r[i] is the minimum value of v[j] in the window, v[j], j=i,...,i+k-1. Thus, if v is the vector 4, 2, 3, 5, 7, 6, ... and k=3 r = 2, 2, 3, 5, ....
We can think of the vector r as being the minimum seen in a window of length k that slides over the vector v. An obvious approach is to maintain the values in the window in a binary tree (preferably balanced). As the window slides over by one index the tree is adjusted by deleting the first value in the window and inserting the new last value. Since inserts and deletes are O(log k) operations the cost of finding r using this method is O(n*log k). We can do better. There is an O(n*log log k) algorithm for determining r which runs as follows:
Let W[i], i=0...k-1 be a vector of values of length k. Define the sequence of ascending mimima, A, for W as follows: Let A be the the mimimum 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]. Thus, for the sequence
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. The expected length of A is log2 k. This follows because the range of values for each A[j] is, on average, half the range of A[j-1]. Whence it follows that searches into A have an average cost of log log k. The idea, then, is to maintain the sequence of ascending minima for the sliding window with a resulting cost which is O(n* log log k).
In its own right the difference between a factor of log k and a factor of log log k is small compared to the difference between k and log k. Thus, if k=1024, log2 k = 10, log2 log2 k ~= 3. It turns out, however, that the implementation of an ascending minima algorithm is quite simple; there is a further gain over using a balanced tree due to simplicity.
Now as to the details. As before let v[i], i=0...n-1 be the basis vector (0 based indexing is simpler here - make the appropriate adjustments for 1 based indexing.) The vector r[i] of length n-k is defined by r[i] = min(v[i+j], j=0,...,k-1).
The vector A is initialized for v[j], j=0,...,k-1. Then r=A. It is convenient to have an associated array J which holds the index in v of the corresponding element in A. (In C you might use a struct to tie the A and J together but that is a programming detail.) It will also be convenient to use a ring buffer to hold A and J. We now consider the update phase.
Suppose that we have determined r[i]. A[j] then holds the ascending minima for v[i+j], j=0,...,k-1. The details of the update are:(1) if (J .eq. i) begin delete A and J and advance the start point of the ring buffer end if (2) if (v[i+k] .gt. the last element in A) begin append v[i+k] to A append i+k to J advance the end point of the ring buffer end if else begin search the ring buffer A for the first element m of A such that A[m] .gt. v[i+k] replace A[m] by v[i+k] replace J[m] by i+k set the end point of the ring buffer to m end elseNotes:
(a) The length of the ring buffer should be k to cover the worst case. If space is not an issue make it of length n so that no index wrapping occurs.
(b) A will never be empty.
(c) The vector A can be omitted since A[m] = v[J[m]]
(d) Initialization can be done using the update algorithm with step 1 omitted.
Note on ring buffers: A ring buffer is an array with indexing that wraps around to the beginning of the array.
Here is a pseudocode implementation of the algorithm. Recode into your language of choice.begin public interface procedure sliding_min arguments (v,r,n,k) dcl v,r; typeof numeric; callby address dcl n,k; typeof int; callby copy assert n .gt. k assert k .gt. 0 end public interface begin procedure sliding_min dcl i; typeof int dcl index; typeof int dcl mid; typeof int dcl low; typeof int dcl high; typeof int dcl ring; typeof int[ring_size] dcl start; typeof int; init 0 dcl stop; typeof int; init 0 dcl ring_size; alias k ring = 0 begin loop i = 1,...,k-1 low = start high = stop begin while (low .le. high) mid = (low+high)/2 if (v[i] .le. v[ring[mid]) high = mid-1 else low = mid+1 end while stop = low ring[stop] = i end loop begin loop i = k,...,n-1 if (ring[start] .eq. i-k) start = mod(start+1,ring_size) low = start if (stop .lt. start) high = stop + ring_size else high = stop begin while (low .le. high) mid = (low+high)/2 index = mod(mid,ring_size) if (v[i] .le. v[ring[index]]) high = mid-1 else low = mid+1 end while stop = mod(low,ring_size) ring[stop] = i r[i-k] = v[ring[start]] end loop end sliding_min
This page was last updated January 10, 2001.
It was archived and declared obsolete May 13, 2009