## Sunday, November 23, 2014

### Data Structure: Sliding Window Minimum / Monotonic Queue

Given an array of elements $$a_0, a_1, a_2, \ldots, a_n$$, and queries Q(i,i+L) which means "find the minimum element in $$a_i, a_{i+1}, \ldots, a_{i+L}$$ ". How can we answer such queries efficiently?

We can have an $$O(n \lg{n})$$ complexity by using a minimum priority queue, RB tree, or a binary tree representation of multiset, but there in this setting we can implement a data structure called monotonic queue which only requires $$O(n)$$ in construction. The implementation of this data structure requires a dequeue.

Let D be the dequeue which maintain a pair of information (i, $$a_i$$). An important property of D that we will maintain is that element in D will always be in sorted order (invariant). We will first start with an empty D, and will insert $$a_i$$ and remove elements from D accordingly as we iterate from the left to the right of array $$a$$ (which is from i = 0, 1, 2, ..., n).

Suppose that we are now at index $$i$$ and considering to add $$a_i$$. Notice that when $$a_i$$ is added, all elements in (j, $$a_j$$) in D such that $$a_j$$ is bigger than $$a_i$$ can never be a minimum value as we go forward, hence they can be removed from D. Furthermore, if the element (i-L-1, $$a_{i-L-1}$$) is in D (which will be located at the top of D if it exists), we remove that element as well. Lastly, we append $$a_i$$ at the back of D. Then we will have Q(i-L, i) = the top element in D when we reach index i. Since each element will enter and leave D only once, we have a total of $$O(N)$$ operations. :D