Solution: Storing Positions, Not Values

The direct way is to compare the leaving value with the front candidate, the way dequeue did in MaxQueue:

if (values[i - k] == candidates.getFirst()) {
  candidates.removeFirst();
}

Consider this window:

array:  [ 8,  8,  1,  1, ... ]
              └───────┘
              the window now covers indices 1, 2, 3

deque:  [ 8, ... ]

The value that just left is values[0], which is 8. The front candidate is also 8. Is it the 8 that left, or the 8 at index 1 that is still inside the window? Looking only at the values, we cannot tell. If the front candidate is the 8 at index 1, removing it is wrong: the window still contains it, and it is the window’s maximum. MaxQueue avoids this by keeping equal values as separate candidates, so that each dequeue of an 8 removes one 8. That works, but the deque then holds duplicates, and the eviction loop has to keep equal values, so it cannot evict with <=.

The problem is that a value does not carry its position. To decide whether the front candidate has left the window, we need to know its index in the array and which indices the window currently covers.

We have run into a similar problem before. In the queue chapter, the Round-Robin Scheduling practice problem needed to know which task sat at the front of the queue. Rather than pairing each task’s time with its index, we stored just the index in the queue and kept the times in a separate array, looking them up when needed. The same approach works here.

So for each candidate we store its index instead of its value. From the index we can get the value with values[index].

Let’s go back to the example we used to build the candidate list:

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

The candidate list went through these stages:

[ 1 ]
[ 3 ]
[ 3, -1 ]
[ 3, -1, -3 ]
[ 5 ]
[ 5, 3 ]

If we store indices instead of values, the stages become:

[ 0 ]
[ 1 ]
[ 1, 2 ]
[ 1, 2, 3 ]
[ 4 ]
[ 4, 5 ]

When we decide what to evict, we compare the values. When we decide what has expired, we check the indices.

The values the candidate indices point to decrease from front to back, so the front index always points to the maximum of the current window.