Monotonic Queue Algorithms (Google Interview)

5 min readApr 14, 2020

This article is about Monotonic Queue data structure as well as algorithmic problems, which can be solved using it, such as ‘Largest Rectangle Area’, ‘132 Pattern’ and others. You can find a list of other problems to practice this topic at the end of the page.

This article will be updated with more problem analyses, meanwhile you can find full solutions to problems in the article in this repository.

Definition

Monotonic Queue is a data structure that keeps it’s elements either entirely in non-increasing, or entirely in non-decreasing order. For some problems just a stack can be of use, although for a more standardized approach we can apply queue (or deque), and from this point forward I will be using the term Monotonic Queue (or MQ for short). Here are some commonly used operations:

Monotonic Queue interface

MQ is mostly used as a dynamic programming optimization technique and for some problems where it is applicable we can reduce the reasoning to finding the nearest element. The advantage of MQ is linear time complexity.

One way to think of how the monotonic queue technique can be applied is to imagine how you can benefit from using increasing or decreasing sequence and what could you calculate having that sequence.

Sample problem

Let’s have a look at the Daily Temperatures problem, in it we are asked to find the next day with bigger temperature for each day. To solve it we are going to use decreasing MQ.

As an example let’s take an array [89, 62, 70, 58, 47, 76, 100]. Below you can find an overview of the nearest biggest elements (to the right) for each element of the array. By doing so, we can pretty much see the result.

For each element from last to first we push elements to MQ. Before actually adding an element to the queue, we remove values which are smaller than the current value, this way we can keep a non-increasing sequence. Then we record the distance to the element at the end of the queue and then we finally add a new element.

Push method

Here is the visual guide, you can see an input array on the left and a queue on the right:

Check out the full solution to this problem right here.

Before stepping into more interesting problems let’s glance at a different approach to search for nearest values. We will be using an array to keep indexes of nearest biggest values. This algorithm was invented not too long ago by Jérémy Barbay and Johannes Fischer, you can find a paper describing it in full here.

The idea is to store the index j of the preceding smaller value of the ith value A[i] in P[i], where P is an array of preceding smaller value indexes:

for i from 1 to n:
    j = i-1
    while A[j] >= A[i]:
        j = P[j]
    P[i] = j

Here is the version of the problem using this algorithm (‘nearest’ array here is the analogy of ‘P’ array from the above):

Implementation using array

Now, let’s continue with the queue..

Largest Rectangle in Histogram

Let’s look at the slides first:

We can take a guess that the largest area would be one of those highlighted rectangles on slides. Also we can say that it will involve one or more full bar lengths. The largest area’s height will be the highest bar of the selected bars or the smaller bar that will cut along other bars that are bigger. We can cut along bigger bars with smaller bar and we can’t cut along smaller bars with the bigger one. Thus the width would be spanning between smaller bars - from the smaller bar on the left to the smaller bar on the right from the current bar.

To solve this, MQ fits right in - we will be using two increasing MQs for that, one for left nearest values and one for right ones. Please check out the code:

Also, here is an optimized version:

You can apply the same idea in the problems Maximal Rectangle and Maximal Square.

132 Pattern

132 Pattern is another interesting problem, we will use essentially the same algorithm with slight modifications. In the task we need to figure out if we have a sequence ai, aj, ak in array such that i < j < k and ai < ak < aj.

One of the ways to go about applying MQ here is to use MQ for ‘13’ out of ‘132’ pattern, which means having a decreasing MQ, going from right to left. Now, let’s look at the first slide - in this case our ‘1’ is 1, ‘3’ is 5 and ‘2’ is 4. We know that the ‘2’ should be between ‘1’ and ‘3’, and the definite ‘2’ (most likely to be the answer) will be the biggest ‘2’ we can find, and the biggest ‘2’ is the last ‘2’ we can remove with ‘3’ from the queue. Then our task is just to find if we have the ‘1’ which is smaller then the ‘2’ we already got.

Shortest Subarray with Sum at Least K

Here sliding window algorithm alone will not work because of negative values (similar problem where it works). We will have to improve sliding window algorithm to use MQ.

Let’s unravel the problem statement. We need to find the shortest subarray min(r - l) so sumAt[r] — sumAt[l] ≥ K (sumAt is a prefix sum array) or find the nearest l so that sumAt[l] ≤ sumAt[r]-K. Using increasing MQ will help us keep the elements of sumAt sorted, when keeping elements such as sumAt[i] where sumAt[i] > sumAt[j] might block the movement of the left window pointer. So, keep increasing MQ, while changing the window(l, r).

for each prefix sum at i push new Item(pre[i], i) to MQ

Check out the full solution to this problem right here.

Thank you for making it till the end!

This article will be updated with more problem analyzes, meanwhile you can find full solutions to problems in the article in this repository.

Monotonic Queue Algorithms (Google Interview)

Definition

Sample problem

Largest Rectangle in Histogram

132 Pattern

Shortest Subarray with Sum at Least K

Other problems to practice

Written by Grigorii Shevchenko

Responses (3)