Daily bit(e) of C++ | Maximum in a sliding window

Daily bit(e) of C++ #28, Common C++ interview problem: Maximum in a sliding window

Today we will look at a common C++ interview problem: Maximum in a sliding window.

Given an array of integers and the size of a sliding window, calculate the maximum for each of the positions of the sliding window.

The output should be empty if there are fewer input elements than the window size.

Your solution should run in O(n) time.

In this example (input {1,2,-3,5,0}, window size 3), the output would be {2,5,5}.

Before you continue reading the solution, try to solve it yourself. Here is a link to Compiler Explorer with a couple of test cases: https://compiler-explorer.com/z/nYMzEv41j.

Solution

There are several ways to approach this problem; I chose one that is reasonably easy to understand.

Let's consider how the local maximums behave. When we encounter a new element, any previously encountered elements with lower values will no longer have a chance to be a local maximum.

We can therefore remember the current candidates, where the candidates leave for two potential reasons:

1. The candidate is the current maximum, and we just moved past its influence.

2. We encountered a new element with a higher value.

We can achieve this with a simple deque, dropping the front element when we pass its influence and dropping the back elements until the back element is larger than the element added to the window.

This leaves the deque sorted without exiting O(n) complexity (as every element is only inserted and removed from the queue once).

Click to open in Compiler Explorer.

---