Sliding window min/max, priority queue & Monotonic Queue

Given 1 D array, how to find the min/max value in a sliding window? We have three ways:

  • O(n²) naive way. two for loops
  • O(n log n) using priority queue + soft deletion
  • O(n) priority queue.

The naive way and priority queue solutions are relatively easy to be understood. Here I’d like to focus on understanding the monotonic queue solution.

Monotonic queue

Think about a simpler question:

what is the maximum value so far in the list {3, 4, 5, 1, 8, 10}

The solution above is pretty nature and pretty straightforward.

How about make it stupid?

using priority queue

Yes, we successfully change the complexity from O(n) to O(n log n) by using a priority queue.

using monotonic queue

We can see by using similar logic as the monotonic queue, we can get the same results with the complexity of O(n) and space complexity is also O(n). Since each time, only one element is put in the deque, we don’t need a deque, we just use an integer variable that will be fine. This explains why we don’t use a deque to solve this problem.

After we get familiar to the monotonic queue solution from a simple example, let’s do something real.

A real problem can be solved by using a monotonic queue

what is the maximum sliding window value so far in the list {3, 4, 5, 1, 8, 10}, the window size should be less or equal to 3?

Now, we can see a slight difference between this one and the above example which does not have any constraints.

increasing monotonic queue

Decreasing monotonic queue

239. Sliding Window Maximum

Video explanation in Chinese can be found in [3]

Naive O(n²) solution got TLE

Priority queue + soft deletion get AC

Multiset solution

Using the monotonic queue idea to improve the multiset code

Actually, we can directly use a deque to implement the monotonic queue solution as shown below:

Monotonic solution. The queue is in increasing order.

1499. Max Value of Equation

decrease deque

increase deque

priority queue solution

multiset solution A

multiset solution B

Some similar problems

A real interview problem

see [1]