# 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 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 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
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
```