In this problem, we are asked to find all sliding-window minima in an array, for some fixed-length window. We are given two passes through the array. The catch is that we are given only $O(\sqrt{N})$ memory.

Let $f(i)$ be the location of the smallest element in the range $[i, i+K)$, breaking ties by smallest index. Observe that $f(i) \leq f(i+1)$ for each $i$. So if we compute $f(0), f(B), f(2B), \dots, f(N)$ for some block size $B$ in the first pass, this gives us some information which we may be able to use in the second pass to compute the remaining $f(i)$s.

Let's ignore the constraint on calls to set/get for now. If we let $B = \sqrt{N}$, then we can compute $f(0), f(\sqrt{N}), \dots, f(N)$ in our first pass using only $O(\sqrt{N})$ memory and $O(N\sqrt{N})$ time. Now, in the second pass, observe that for any fixed array element $i$, there are only $O(\sqrt{N})$ windows for which the minimum could possibly be at position $i$.

This suggests the following algorithm for the second pass: read and ignore all elements with index less than $f(0)$. Now maintain running minima for $f(0), f(1), f(2), \dots, f(\sqrt{N})$. Once we've read in the element with index $f(\sqrt{N})$, we know that we have computed the correct minima for the first $\sqrt{N}$ windows. Output these, start maintaining minima for the next $\sqrt{N}$ windows, and continue in the same fashion.

The memory usage of the second pass is also $\sqrt{N}$, as desired. Unfortunately, the time complexity of each pass is $O(N \sqrt{N})$. In particular, the above algorithm would use $O(N \sqrt{N})$ calls to set and get, which would exceed the given bound. To improve the time complexity, we can use a monotonic queue in each pass. In the first pass, for instance, the boundaries of the $\sqrt{N}$ windows define $2\sqrt{N}$ subarrays, and for each subarray we can simply compute the minimum of the subarray and put that into the monotonic queue. The length of the monotonic queue therefore never exceeds $O(\sqrt{N})$, and we can compute the $\sqrt{N}$ minima-locations in $O(N)$ time. For the second pass, it suffices to observe that in each segment of the array (say, between $f(i\sqrt{N})$ and $f((i+1)\sqrt{N})$) all but $O(\sqrt{N})$ of the array elements are in all $\sqrt{N}$ windows of interest. This once again allows us to improve the pass to $O(N)$ time will not exceeding $O(\sqrt{N})$ memory.

Below is an implementation of the above algorithm.

#include "grader.h" #define BLOCK 1000 #define DIF 4050 // VARIABLE - LOCATION IN BESSIE'S NOTEBOOK // back index - 0 // top index - 1 // queue (2,3) (4,5) ... // (index, value) // current block's endpoint index (divided by BLOCK) - DIF-1 // current block's global low - DIF-2 // number of minima output - DIF-3 void helpBessie(int v) { int N = getTrainLength(); int K = getWindowLength(); int i = getCurrentCarIndex(); int p = getCurrentPassIndex(); if(p==0) { if(i==0) { set(0,0); set(1,-1); } int top = get(1); int back = get(0); if(i%BLOCK == 0 || (i>=K && (i-K)%BLOCK == 0)) // reached boundary of some window { // need to make new entry in monotonic queue while(top >= back && get(2*top+3) >= v) top--; top++; set(2*top+2,i); set(2*top+3,v); } else //still part of same subarray; just update the top entry of monotonic queue { int curTopValue = get(2*top+3); if(v <= curTopValue) { top--; while(top >= back && get(2*top+3) >= v) top--; top++; set(2*top+2,i); set(2*top+3,v); } } if(i >= K-1 && (i+1-K)%BLOCK == 0) // at endpoint of some window; need to store location of minimum { while(top >= back && get(2*back+2) <= i-K) // pop from back end up queue until queue contains only back++; // elements in desired window set(DIF + (i+1-K)/BLOCK, get(2*back+2)); // store location of minimum } set(0,back); set(1,top); } else { if(i < get(DIF)) return; if(i == get(DIF)) { set(0,0); set(1,-1); set(DIF-1, 1); set(DIF-2,1000000000); set(DIF-3, 0); } int bc = get(DIF-1); int top = get(1); int back = get(0); int outputs = get(DIF-3); if(i - get(DIF+bc-1) <= BLOCK) // element may not be contained in all relevant windows { // so add to monotonic queue while(top >= back && get(2*top+3) >= v) top--; top++; set(2*top+2,i); set(2*top+3,v); } else // element is contained in all relevant windows { // so we can update a global minimum int globalLow = get(DIF-2); if(v < globalLow) set(DIF-2,v); } if(outputs + K - 1 == i) //need to output a minimum { while(top >= back && get(2*back+2) < outputs) back++; shoutMinimum(min(get(DIF-2),get(2*back+3))); outputs++; } while(BLOCK*bc + K-1 < N && get(DIF+bc) == i) // reached boundary of current subarray { while(outputs <= BLOCK*bc) // output minimums for all remaining windows in current block { while(top >= back && get(2*back+2) < outputs) back++; shoutMinimum(min(get(DIF-2),get(2*back+3))); outputs++; } bc++; set(DIF-2,1000000000); top = back = 0; set(2*top+2,i); set(2*top+3,v); } set(DIF-3,outputs); set(DIF-1,bc); set(1,top); set(0,back); } }