The proportions of Americans who are politically affiliated with one of the two major parties has been very stable over the last 20 years, at about 60% with a slight downward trend (+ marks and thick trend line in the chart below). Over the same period, the general outlook of the public has fluctuated wildly, with those who say the country is “going in the right direction” reaching over 50% at one point and falling 5 years later to 20% (circles and thin trend line). The public mood seems to be optimistic immediately following presidential elections (vertical dashed lines), and pessimistic immediately before them.

Data source: New York Times/CBS poll, April 15-20, 2011.

The following C++ code takes a sequence of n elements, a1, a2, …, an, and outputs a sequence of n – k + 1 elements. The i-th output element is a maximal element in the subsequence ai, ai + 1, …, ai + k – 1. The runtime complexity of the code is O(n).

template <typename T>
void insert(std::list< std::pair<T,unsigned int> > &l, T v)
{
    unsigned int sp = 0;
    while (!l.empty() && l.back().first < v)
    {
        sp++;
        l.pop_back();
    }
    l.push_back(std::pair<T,unsigned int>(v,sp));
}

template <typename T>
void advance(std::list< std::pair<T,unsigned int> > &l)
{
    if (l.front().second > 0)
        l.front().second--;
    else
        l.pop_front();
}

template <typename T>
void max_in_window(T const *in, T *out, size_t n, size_t k)
{
    std::list< std::pair<T,unsigned int> > l;
    unsigned int i;
    for (i = 0; i < k - 1 && i < n; i++)
        insert(l,in[i]);

    for (; i < n; i++)
    {
        insert(l,in[i]);
        out[0] = l.front().first;
        out++;
        advance(l);
    }
}

Interestingly, an algorithm for the median in a sliding window will have runtime of at least O(n log k), since such an algorithm can be used to sort O(n / k) sequences of length O(k) each:

Let a1, a2, …, an be a sequence of numbers in a known interval, say (0, 1). Create a sequence of length 3n – 2 by padding the sequence with a prefix of (n – 1) 0‘s and a suffix of (n – 1) 1‘s. Now execute the sliding window median algorithm with the padded sequence as input, and with k = 2n – 1.

The i-th output element will be the median of a sequence that is made of the entire sequence a1, a2, …, an, n – i zeros, and i – 1 ones. That median is a(i), the i-th smallest elements of the sequence a1, a2, …, an. Thus, the output of the algorithm will be the sorted sequence a(1), a(2), …, a(n).