Solution: Keeping the Candidates

Recall how the scan found the maximum. The queue held 7, 2, 5, 1, 4, and 7 left. The answer became 5, and the only way to find it was to scan the four items that remained.

But we could have known it ahead of time. Whatever happens, 7 leaves before 2, 5, 1, and 4 do, because it arrived before them. So the moment 7 leaves, the answer is the largest of 2, 5, 1, and 4, and we could have worked that out while they were arriving. Let’s go through the arrivals one at a time and ask one question about each item in the queue: could this item ever be the answer to getMax? If it could, we keep it in mind. If it could not, we evict it.

We enqueue 7. It is the only item, so it is the answer right now.

[ 7 ]

We enqueue 2. The answer is still 7. Could 2 ever be the answer? Yes. If 7 leaves before anything larger than 2 arrives, then 2 is the largest item left. So we keep 2 in mind, after 7.

[ 7, 2 ]

We enqueue 5. The answer is still 7. Could 2 ever be the answer now? No. The 5 arrived after 2, so 5 leaves after 2 does. As long as 2 is in the queue, 5 is in the queue too, and 5 is larger. So getMax would report 5, not 2, at every moment 2 is present. We can evict 2. Could 5 ever be the answer? Yes, once 7 leaves. We keep 5, after 7.

[ 7, 5 ]

The 2 was evicted because a larger item arrived after it. That is the rule: an item can be the answer only while nothing larger has arrived after it. The moment something larger arrives, it can be evicted for good.

We enqueue 1. It is smaller than 5, so 7 and 5 both stay. Could 1 ever be the answer? Yes, once 7 and 5 have left and if nothing larger arrives first. We keep 1, after 5.

[ 7, 5, 1 ]

We enqueue 4. It is larger than 1, so 1 can be evicted: 4 leaves after 1 does, and 4 is larger. It is smaller than 5, so 5 stays. Could 4 ever be the answer? Yes, once 7 and 5 have left.

[ 7, 5, 4 ]

So of the five items in the queue, only three could ever be reported by getMax. We will call the items we keep in mind the candidates. We keep the candidates in the order they arrived, oldest on the left, newest on the right. Two properties hold at every step:

  1. The values never increase from left to right. Each candidate is at least as large as every candidate after it, because otherwise it would have been evicted.
  2. The leftmost candidate is the answer to getMax. It is the largest candidate, and every item that is not a candidate is smaller than some candidate.

Both come from the rule for adding a candidate: before we add a new item on the right, we evict every candidate on the right that is smaller than it. This is the rule the monotonic stack’s push follows in the stack chapter’s practice problems: evict every smaller item from the top, then add the new one.

Now the items start leaving. Dequeue removes 7 from the queue. The 7 is the leftmost candidate, and it is no longer in the queue, so it has to leave the candidate list too. The new leftmost candidate is 5, and that is the answer we needed.

[ 5, 4 ]

The next dequeue removes 2 from the queue. The 2 is not a candidate, since we evicted it when 5 arrived. The candidate list does not change. The dequeue after that removes 5, which is the leftmost candidate, so it leaves the list.

[ 4 ]

Look at where each change happens in the list:

  • When a new item arrives, we evict the smaller candidates on the right, then add the new one on the right.
  • The answer is always the leftmost candidate, so we read it from the left.
  • When the item leaving the queue is the leftmost candidate, we remove it from the left.

So the list is changed at both ends.

We never touch the middle of this list. So a deque may be the right structure for the candidates after all: it adds and removes at both ends, and that is all the candidate list needs.