The minimum on a sliding window algorithm

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[0] 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[0]=A[0]. 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[0] .eq. i) begin
                delete A[0] and J[0] 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 else

Notes:

(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] = 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