Solution: Keeping the Candidates

In MaxQueue we also had to recover the next maximum when the current one leaves, and we solved it by keeping the candidates: the items that could still be reported as the maximum. An item is a candidate while no larger item has arrived after it. When a larger item arrives, the smaller candidates before it are evicted. When the front item leaves the queue, it leaves the candidate list too if it is the front candidate.

The window is a queue. On each slide, one value enters at the right and the earliest value leaves at the left. So the same candidate rule works here. Let’s build the candidate list for the running example and show the window next to it:

values = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

We read 1. It is the only value, so it is the only candidate.

window:      [ 1 ]
candidates:  [ 1 ]

We read 3. It is larger than 1 and arrived later, so 1 is evicted.

window:      [ 1, 3 ]
candidates:  [ 3 ]

We read -1. It is smaller than 3, so it joins the candidates after 3. The first window is now full, and its maximum is the front candidate, 3.

window:      [ 1, 3, -1 ]
candidates:  [ 3, -1 ]

Now the window slides. The value -3 enters and the value 1 leaves. The -3 is smaller than -1, so it joins the candidates at the back. The 1 was evicted when 3 arrived, so the candidates stay as they are when it leaves. The maximum is still 3.

window:      [ 3, -1, -3 ]
candidates:  [ 3, -1, -3 ]

Slide again. The value 3 leaves and the value 5 enters. The 3 was the front candidate, so it leaves the candidates too. The 5 is larger than -3 and -1, so both are evicted before 5 is added. The maximum is 5.

window:      [ -1, -3, 5 ]
candidates:  [ 5 ]

Slide again. The value 3 enters and -1 leaves. The 3 is smaller than 5, so it joins at the back. The -1 was evicted when 5 arrived. The maximum is 5.

window:      [ -3, 5, 3 ]
candidates:  [ 5, 3 ]

So far, every front candidate that left the window was smaller than the value that entered. That is not always the case. Look at this example:

values = [8, 1, 1, 1], k = 3

The 8 is the front candidate, and it stays the front candidate when the two 1s arrive. Then the window slides: another 1 enters and the 8 leaves. No larger value removed it. It left because the window slid past it, and it has to leave the candidate list from the front, the way the front item leaves the candidates in MaxQueue when it is dequeued.

window:      [ 8, 1, 1 ]        window:      [ 1, 1, 1 ]
candidates:  [ 8, 1 ]           candidates:  [ 1 ]

So the candidate list changes at both ends, as in MaxQueue, and we keep the candidates in a deque.

Here the array takes the place of MaxQueue’s items deque. The window is values[i - k + 1] through values[i], and the value that leaves on a slide is values[i - k]. So we do not need a second deque for the window. We still need a way to tell whether the front candidate is the value that just left.