Skip to main content

Introduction to monotonic stacks and queues (with LeetCode problems and more)

Daniel Farlow
Software Engineer

Monotonic stacks and queues have a reputation for being notoriously difficult. Why? I suspect the difficulty lies not in what these data structures are but how they are often used to craft solutions to various problems.

This post explores monotonic stacks and queues by first exploring the next greater height problem without any framing whatsoever (i.e., there's no mention of explicitly using a monotonic data structure in any capacity). We then try to use one of the approaches developed for solving the next greater height problem to solve another problem: the sliding window minimum. But our previously developed approach is not quite enough. We need to make a small tweak that turns out to be quite insightful (this leads us to monotonic deques or "monotonic double-ended queues").

The approaches developed for solving both problems are used to set the stage for explaining what monotonic stacks and queues are in a technical sense and why we may want to consider using them in service of solving different kinds of problems. General code templates are provided for maintaining monotonically increasing/decreasing stacks and deques. If you are able to follow the solutions for the introductory problems (i.e., next greater height and sliding window minimum), then you will already know the core of what you need to know about monotonic stacks and deques before being explicitly told their definitions.

Several LeetCode problems are provided where monotonic stacks and/or deques serve as natural tools in crafting optimal solutions (several problems are solved using the concepts fleshed out in this post). An "epilogue" is included at the end of this post, where one problem of notable difficulty is thoroughly examined and solved efficiently by creative use of a monotonic stack.

TLDR

Read the important observations section if you don't have time for much else.


Stacks and queues are defined by their interfaces (e.g., push, pop, pop left, peek, etc.). Monotonicity is not. The following are all examples of monotonic stacks, where the removal of values needed to maintain the monotonic invariant (i.e., strictly/weakly increasing/decreasing) is illustrated in the context of adding 5 to each value collection:

Strictly decreasing
[12, 10, 9, 5, 3, 2, 1] # Before addition of 5
[12, 10, 9, 5] # After addition of 5
Weakly decreasing
[12, 10, 10, 9, 5, 3, 1, 0] # Before addition of 5
[12, 10, 10, 9, 5, 5] # After addition of 5
Strictly increasing
[0, 1, 3, 5, 6, 10, 11] # Before addition of 5
[0, 1, 3, 5] # After addition of 5
Weakly increasing
[1, 2, 2, 3, 5, 7, 8, 10] # Before addition of 5
[1, 2, 2, 3, 5, 5] # After addition of 5

The removals above are all stack-like in nature (i.e., popping and pushing from the right), which is why the term "monotonic queue" can be rather misleading. If elements need to be removed from the left, then we use a double-ended queue or deque (e.g., see Python's deque from its collections module). Stack-like operations (push and pop) are always performed on the right end to maintain the monotonic invariant. If the queue-like operation of removing an element from the left end (pop left) is needed, then we can use a deque instead of a simple stack (this allows us to still use stack-like operations to maintain the monotonic invariant while also allowing us to pop elements from the left, as needed).

What can make monotonic stacks and deques challenging at first is not what they are (all possibilities are shown above) but how they are used in sophisticated ways to solve problems of varying complexity. This post thoroughly explores two introductory problems and various approaches to solving these problems without ever mentioning the words monotonic, stack, queue, or deque (double-ended queue). The ideas behind these structures are used though, where an emphasis is placed on trying to use these ideas as organically as possible (i.e., not getting mired in technical mumbo jumbo but exploring new ways of thinking). If you can make it through the "next greater height" and "sliding window minimum" introductory problems, then you will largely know what you need to know about monotonic stacks and deques.

Template quick access ("next" and "previous" value templates and illustration of monotonic deque)
Combined templates for finding previous and next values in a single pass
def fn(nums):
n = len(nums)
ans = [[-1, -1] for _ in range(n)] # default values for missing PREVIOUS and NEXT values, respectively
stack = [] # monotonic stack

# the comparison operator (?) dictates what each element's PREVIOUS and NEXT values will be
# (<=) PREVIOUS larger value and NEXT larger or equal value (strictly decreasing stack)
# (<) PREVIOUS larger or equal value and NEXT larger value (weakly decreasing stack)
# (>=) PREVIOUS smaller value and NEXT smaller or equal value (strictly increasing stack)
# (>) PREVIOUS smaller or equal value and NEXT smaller value (weakly increasing stack)
for i in range(n):
while stack and nums[stack[-1]] ? nums[i]:
# NEXT values processed
idx = stack.pop()
ans[idx][1] = i # use nums[i] instead of i to directly record array values instead of indexes
# PREVIOUS values processed
ans[i][0] = -1 if not stack else stack[-1] # use nums[stack[-1]] instead of stack[-1]
# to directly record array values instead of indexes
stack.append(i)

return ans
Template for finding A's next value B
def fn(nums):
n = len(nums)
ans = [None] * n
stack = [] # monotonic stack
for i in range(n):
val_B = nums[i]
# the comparison operator (?) dictates what A's next value B represents
# (<) next larger value (weakly decreasing stack)
# (<=) next larger or equal value (strictly decreasing stack)
# (>) next smaller value (weakly increasing stack)
# (>=) next smaller or equal value (strictly increasing stack)
while stack and nums[stack[-1]] ? val_B:
idx_val_A = stack.pop()
ans[idx_val_A] = val_B
stack.append(i)

# process elements that never had a "next" value that satisfied the criteria
while stack:
idx_val_A = stack.pop()
ans[idx_val_A] = -1

return ans
Template for finding A's previous value B
def fn(nums):
n = len(nums)
ans = [None] * n
stack = [] # monotonic stack
for i in range(n):
val_A = nums[i]
# the comparison operator (?) dictates what A's previous value B represents
# (<=) previous larger (strictly decreasing)
# (<) previous larger or equal value (weakly decreasing)
# (>=) previous smaller value (strictly increasing)
# (>) previous smaller or equal value (weakly increasing)
while stack and nums[stack[-1]] ? val_A:
stack.pop()

if stack:
idx_val_B = stack[-1]
val_B = nums[idx_val_B]
ans[i] = val_B
else:
ans[i] = -1

stack.append(i)

return ans
Monotonic deque (weakly decreasing)
from collections import deque
def fn(nums):
queue = deque() # monotonic deque (weakly decreasing)
ans = []

for i in range(len(nums)):
curr_num = nums[i]
while queue and nums[queue[-1]] < curr_num:
queue.pop()
queue.append(i)

if CONDITION:
queue.popleft()

return ans
Note about monotonic deque

The code in the template above is virtually the same as the code used to maintain a monotonic stack (weakly decreasing) with one notable exception:

def fn(nums):
dec_stack = []
ans = []

for i in range(len(nums)):
curr_num = nums[i]
while dec_stack and nums[dec_stack[-1]] < curr_num:
dec_stack.pop()
dec_stack.append(i)




return ans

The highlighted block above with nothing in it shows how the code that triggers popping an element from the left based on some CONDITION has been removed. That's generally the only notable difference between code that uses a stack versus that which uses a deque.

Contents

Next greater height

Perhaps the best way to start our exploration of monotonic stacks/queues is by considering a problem with no framing (i.e., we'll worry about what monotonic stacks/queues actually are at a later point). This video introduces monotonic stacks with the problem of finding the next greater height value (left to right) for a row of people lined up (or -1 if a next greater height does not exist):

The heights, heights = [12, 11, 12, 14, 13], are listed above each person in magenta, and the final reported answer is the cyan box on the bottom: ans = [14, 12, 14, -1, -1]; that is, the next greater height for the first person of height 12 is the fourth person of height 14, and the next greater height for the second person of height 11 is the third person of height 12, and so on. Let's go through some solution approaches for obtaining these answers.

Approach 0 (brute force)

How would you solve this problem if you were out in the wild (i.e., if you really had a row of people in front of you with their heights labeled above them)? You would probably do what I would do along with most other people:

  • Start with the first (leftmost) person. Then move left to right across the row (beginning at the second person) until you've identified a person with a height greater than the first person. Record that height (or -1 if the search was unsuccessful).
  • Start with the next (second) person. Move left to right across the row (beginning at the third person) until you've identified a person with a height greater than the second person. Record that height (or -1 if the search was unsuccessful).
  • Start with the next (third) person. And so on.

This brute force approach is intuitive and not too difficult to implement with code (we pre-fill the answer array with -1 to avoid having to manually make such assignments after unsuccessful searches):

def next_greater_height_0(heights):
# pre-fill the answer array with -1
ans = [-1] * len(heights)

# start with the leftmost person
for i in range(len(heights) - 1):
curr_height = heights[i]

# begin looking for the next greater height
for j in range(i + 1, len(heights)):
next_height = heights[j]

# if a greater height is found, update the answer array
if curr_height < next_height:
ans[i] = next_height
break

return ans

What's the computational burden of the approach above (i.e., what is the time and space complexity of the next_greater_height_0 function)?

  • Time If heights has nn elements, then how many total iterations can we possibly perform? The worst-case scenario is if the heights input array is strictly decreasing (because then no height will have a next greater height and we must exhaust the search space every time we look for a next greater height). Our function appears to be O(n2)O(n^2) in terms of time complexity, but let's confirm this — the inner loop is where the heavy lifting is done. How many times can we possibly enter the innermost loop and perform an operation in the worst-case scenario? The table below shows how many times the innermost loop can fire (i.e., how many elements are traversed or "people searched" in service of looking for a next greater height for index i):

    i index012n3n2j iterationsn1n2n321\begin{array}{l|cccccc} i\ \text{index} & 0 & 1 & 2 & \cdots & n-3 & n-2\\\hline j\ \text{iterations} & n-1 & n-2 & n-3 & \cdots & 2 & 1 \end{array}

    We can have a total of (n1)+(n2)++2+1(n-1) + (n-2) + \cdots + 2 + 1 iterations. This is the sum of the first n1n-1 positive integers. Since the sum of the first nn positive integers is given by the formula n(n+1)/2n(n+1)/2, we can see that our sum amounts to (n1)((n1)+1)/2=n(n1)/2=O(n2)(n-1)((n-1) + 1) / 2 = n(n-1)/2 = O(n^2), as expected. Hence, the brute force approach above is O(n2)O(n^2) in terms of time complexity.

  • Space: For space complexity, no additional memory is consumed as the size of the input array heights scales to infinity; hence, the space complexity is O(1)O(1).

There's nothing wrong with the approach above. But a time complexity of O(n2)O(n^2) is often not considered to be that great unless it's completely unavoidable. Is this completely unavoidable when trying to solve this problem?

Approach 1 (right to left, single pass)

Is there a way to improve on the O(n2)O(n^2) time complexity for the brute force solution above? Is it possible for us to compromise on space to get a solution that is O(n)O(n) time and O(n)O(n) space (e.g., the same compromise is made for the intended solution to LC 1. Two Sum), where we maintain some sort of data structure to help us figure out each person's next greater height? Maybe. Let's see if we can figure this example problem out manually/verbally first before coding anything up.

Process description

If we started processing the height of each person from the right, then maybe we could use the heights we've seen thus far to determine the next greater height for each element as we proceed from right to left. Here's one possible way we could do this (the people-indexing is 0-based), first recalling the heights of the people to be processed, heights = [12, 11, 12, 14, 13]:

PersonHeightProcess Description
413This is the rightmost person so there cannot be another person to the right with a greater height. We report -1 for this person since there is no next greater height, and we store the height we've just seen so we can reference it later, if needed: [13].
314What heights have we seen thus far? We have [13] and that's it. But that's not greater than 14. So we report -1 for this person too. How should we store the height of 14 we've just encountered so that we can effectively reference it later, if needed? Should we still keep the 13 in the collection of heights we've seen so far: [13]? No, because any height that could have 13 as its next greater height would certainly have 14 as its actual next greater height since 14 comes before 13 in the left-to-right row of people. It does not benefit us at all to keep the 13 so we remove it. Then we add 14: [14].
212Do we have a height greater than 12 that we can reference that might be a candidate for its next greater height? Yes! We can finally use our small collection [14] effectively. The height of 14 is the next greater height. So we report 14 for this person. What should we do with the height of 12 we just saw? Should we add it to our collection or not? If we didn't add it to our collection, then we could potentially see a height in the near future that is smaller than 12, say 1, and reporting 14 as the next greater height would be inaccurate (because 12 would actually be the next greater height). So we should add 12 to the collection: [14, 12].
111Do we have a height greater than 11 that we can reference that might be a candidate for its next greater height? Yes! Our collection right now is [14, 12], but the 14 comes after the 12 in terms of the order in which these heights are encountered; hence, we will report 12 for this person. What should we do with the height of 11? For the same reasons as noted above, we should add 11 to our collection: [14, 12, 11].
012Do we have a height greater than 12 that we can reference that might be a candidate for its next greater height? Yes! Our collection right now is [14, 12, 11]. How does this help? Because of how we've arranged the collection (from biggest height to smallest and in the order we've encountered them). This means we first test 11 as a candidate. It's not greater than 12 so we remove it from our collection: [14, 12]. What about 12? It is also not greater than 12 so we remove it from our collection too: [14]. What about 14? It is greater than 12 so we will report 14 as the next greater height for this person. We now add 12 to our collection and continue to process heights as we've been doing. But we're now at the end of the row of people we're considering for this specific example; hence, the state of our final collection we've been maintaining is as follows: [14, 12].

It may be illustrative to show a condensed table where the reported next greater height for each person is included as well as what our height reference collection looks like after processing each person:

PersonHeightNext greater heightHeight collection after person processed
413-1[13]
314-1[14]
21214[14, 12]
11112[14, 12, 11]
01214[14, 12]

Code implementation

Now for the code implementation of the process described above:

def next_greater_height_1(heights):
height_collection = []
ans = [None] * len(heights)
for i in range(len(heights) - 1, -1, -1):
curr_height = heights[i]

# remove all height collection references less than or equal to the current height
while height_collection and height_collection[-1] <= curr_height:
height_collection.pop()

# if collection of height references is empty, then there's no next greater height: -1
if not height_collection:
ans[i] = -1

# if height collection is non-empty, then next greater height must be the
# most recently seen height in our collection that is greater than the current height
else:
ans[i] = height_collection[-1]

# add the current height to the height collection,
# which is guaranteed to be less than all other heights in the collection
height_collection.append(curr_height)

return ans

Code implementation confirms process description

The code above closely follows the process described previously; in fact, if we add a simple print statement at the end of each for loop iteration (i.e., after each person has been processed), then we can see this more clearly for ourselves:

print(
f'Person: {i}; '
f'Height: {curr_height}; '
f'Next greater height: {ans[i]}; '
f'Height collection: {height_collection}; '
f'Answer so far: {ans}'
)

The console output then confirms the work we did previously (horizontal spacing adjustments added after printing):

Person: 4;  Height: 13;  Next greater height: -1;  Height collection: [13];          Answer so far: [None, None, None, None, -1]
Person: 3; Height: 14; Next greater height: -1; Height collection: [14]; Answer so far: [None, None, None, -1, -1]
Person: 2; Height: 12; Next greater height: 14; Height collection: [14, 12]; Answer so far: [None, None, 14, -1, -1]
Person: 1; Height: 11; Next greater height: 12; Height collection: [14, 12, 11]; Answer so far: [None, 12, 14, -1, -1]
Person: 0; Height: 12; Next greater height: 14; Height collection: [14, 12]; Answer so far: [14, 12, 14, -1, -1]

Approach 2 (left to right, single pass)

The approach described above was kind of clever, specifically how we kept a sort of "history" or collection of previous heights encountered to facilitate the determination of each person's next greater height. Iterating from right to left can sometimes provide a number of advantages, and that's on full display in the solution approach above. But something worth considering is whether or not it's even possible to solve this problem by iterating from left to right in a single pass; that is, we'd like to keep our computational improvement from O(n2)O(n^2) to O(n)O(n), and we're still willing to compromise on the space requirement from O(1)O(1) to O(n)O(n), but we'd like to move from left to right, if possible.

Process intuition

Iterating from left to right to solve the next greater heights problem is possible, but we need to get a little more creative in how we keep track of the heights we've seen thus far to facilitate "next greater height" determinations. Recall the heights we're trying to process: heights = [12, 11, 12, 14, 13]. How we actually start processing peoples' heights from left to right presents a clear problem: what do we do with the first 12 we encounter? When iterating from right to left, it was very clear what to do with the 13 that we encountered on the first iteration: it couldn't possibly have a next greater height (it represented the height of the rightmost person). That's not the case here with the 12 on the first iteration from left to right. It's not just possible for this height to have a next greater height — we know this height has a next greater height of 14, but we need some way of easily determining that. How? What's the strategy?

Part of the strategy harkens back to the intuitive strategy employed in the brute force approach: the next height we see that is greater than the current height becomes the current height's next greater height. If we start with 12, then we cannot yet make a determination about what its next greater height is. So let's just try to "remember" somehow that this height still needs a next greater height.

We could model the situation as follows, where we start by placing an "answer box" below each person's height. The value in the box, if present, represents that person's next greater height. For example, the first person of height 12 would have 14 in its answer box since the next greater height for the first person is the person with a height of 14. Our job is to fill in all answer boxes somehow. The boxes below illustrate this description from our starting state (all empty answer boxes) to our ending state (all answer boxes filled with values reflective of our previous work, which we know to be correct):

Starting state
  12   11   12   14   13 
---- ---- ---- ---- ----
| | | | | |
---- ---- ---- ---- ----
Final state
  12   11   12   14   13 
---- ---- ---- ---- ----
| 14 | 12 | 14 | -1 | -1 |
---- ---- ---- ---- ----

As noted above, we cannot yet make a determination for the leftmost 12 so we'll simply fill its answer box with ?? until we have more information we can act on:

After first iteration
  12   11   12   14   13 
---- ---- ---- ---- ----
| ?? | | | | |
---- ---- ---- ---- ----

In fact, for every current height we encounter, it is not possible for us to know its next greater height yet since we're iterating from left to right. Consequently, each current height we encounter should have its answer box filled with ??. The real question is whether or not any previously encountered heights have the current height as their next greater height; that is, whenever we encounter a new height as the current height, we should look at all heights previously whose answer boxes hold ?? and see if the current height is greater (if so, then this height becomes the next greater height for all such previous heights). This may sound confusing at first, but working out the mechanics for the rest of this example will help clarify the process.

For the new current height of 11, we fill its answer box with ??, and we can see all previous heights whose answer boxes hold ?? (just the leftmost 12 in this case) are not less than 11; hence, no updates are needed and we move on:

After second iteration
  12   11   12   14   13 
---- ---- ---- ---- ----
| ?? | ?? | | | |
---- ---- ---- ---- ----

Now we encounter the second 12. We fill its answer box with ?? and we look at previous heights whose answer boxes hold ??. The only height less than 12 whose answer box has ?? is the 11 we encountered in the previous iteration. Its next greater height must be 12. We make the update to the answer box for 11 and move on:

After third iteration
  12   11   12   14   13 
---- ---- ---- ---- ----
| ?? | 12 | ?? | | |
---- ---- ---- ---- ----

What about the new height of 14? The heights of 12 encountered previously both have 14 as their next greater height. We make the updates and move on:

After fourth iteration
  12   11   12   14   13 
---- ---- ---- ---- ----
| 14 | 12 | 14 | ?? | |
---- ---- ---- ---- ----

For the 13, it is clear no previous height has 13 as its next greater height. Hence, the (almost) final state of the answer boxes is as follows:

After fifth (and final) iteration
  12   11   12   14   13 
---- ---- ---- ---- ----
| 14 | 12 | 14 | ?? | ?? |
---- ---- ---- ---- ----

The only thing left to do to reach the desired final state is to replace all ?? remaining in answer boxes with -1 (since all such heights have no next greater heights once we've made a full pass iterating from left to right):

Final state
  12   11   12   14   13 
---- ---- ---- ---- ----
| 14 | 12 | 14 | -1 | -1 |
---- ---- ---- ---- ----

And we're done! How can we get started on translating the process outlined above into an actual code implementation? Two points are probably worthy of consideration before embarking on this task:

  • -1 autofilling: This is a minor point, but the last step above where we had to convert all remaining ?? to -1 is unnecessary. The solution approach outlined in the previous section autofilled the answer array with None: ans = [None] * len(heights). And that was fine for that solution because the answer slot for every single height was updated to be the next greater height or -1 if no such height existed.

    For the process we've described above, however, we only update an answer box if we've found a next greater height; hence, we can simply initialize the answer array with -1 and overwrite answer slots if we find next greater heights.

  • Updating the next greater height for previous heights based on the current height: This is a more pressing issue. Specifically, the transition from "after the third iteration" to "after the fourth iteration" may raise some eyebrows depending on how we actually plan to do this with code:

    After third iteration
      12   11   12   14   13 
    ---- ---- ---- ---- ----
    | ?? | 12 | ?? | | |
    ---- ---- ---- ---- ----
    After fourth iteration
      12   11   12   14   13 
    ---- ---- ---- ---- ----
    | 14 | 12 | 14 | ?? | |
    ---- ---- ---- ---- ----

    We need to execute this transition efficiently somehow. If we tried updating the answer boxes by iterating from left to right from each height without a next greater height to the current height, then that process would look like the following:

    • person 12 has an empty answer box: update to 14
    • person 11 has a non-empty answer box: skip
    • person 12 has an empty answer box: update to 14
    • person 14 is the current height: stop

    Imagine if we had to follow the process above every time we encountered a new height. The time complexity would end up being similar to that of the brute force approach. That is not what we want. But for our current consideration we still need to be able to refer to the height values of 12 somehow in order to update their answer boxes to 14. How can we do this as efficiently as possible?

    In the previous solution approach, we maintained a collection of heights that decreased from left to right. For example, the collection [14, 12, 11] represented heights that we encountered from oldest to newest, largest to smallest. And we removed smaller heights as needed until we encountered a height greater than the current height. But that approach will not work here. We need to update both answer boxes for the height of 12 — simply keeping a single height of 12 in some sort of collection will not suffice because there's no way to distinguish between these two heights based on value alone.

    How can we make a distinction between two heights that have the same numeric value? Consider the original input array: heights = [12, 11, 12, 14, 13]. It may be true that heights[0] == heights[2] (i.e., 12 == 12), but it's certainly not the case that 0 == 2; that is, the index values of the heights make each height uniquely distinct. What if instead of keeping a collection of heights for reference we kept a collection of index values for previously encountered heights? Index values make it possible to access both a height's numeric value as well as where its answer box needs to be updated (i.e., its indexed position). This might be just what we need.

Process description

If we started processing the height of each person from the left using the process alluded to above, where we kept track of index values for previously encountered heights, then what would each step of the process look like? Let's draw this up in tabular form, as with the previous solution approach (the people-indexing is 0-based), first recalling the heights of the people to be processed, heights = [12, 11, 12, 14, 13]. (An index-to-height correspondence array is provided in the table below to help clarify what heights correspond to which indexes.)

PersonHeightProcess Description
012This is the leftmost person, and the collection of index values for previously encountered heights is currently empty. Hence, we add the current height's index value to the collection: [0].

Collection's index-to-height correspondence: [12]. Current answer array: [-1, -1, -1, -1, -1].
111The current height is now 11. Are there any index values in the collection that represent a height less 11? No. We now add the current height's index value to the collection: [0, 1].

Collection's index-to-height correspondence: [12, 11]. Current answer array: [-1, -1, -1, -1, -1].
212The current height is now 12. Are there any index values in the collection that represent a height less than 12? Yes. Our current collection is [0, 1], and the index value of 1 corresponds to a height of 11. We update the corresponding slot in the answer array by using our collection of index values (i.e., the next greater height for the person with height 11 is the current height of 12): ans[1] = 12. We now remove 1 from the collection since the person's next greater height at this position has now been determined. Current collection: [0].

Is the height of the person at index 0 less than the current height of 12? No. We now add the current height's index value to the collection: [0, 2].

Collection's index-to-height correspondence: [12, 12]. Current answer array: [-1, 12, -1, -1, -1].
314The current height is now 14. Are there any index values in the collection that represent a height less than 14? Yes. Our current collection is [0, 2], and the index value of 2 corresponds to a height of 12. We update the corresponding answer slot by using our collection of index values (i.e., the next greater height for the person at index 2 with height 12 is the current height of 14): ans[2] = 14. We now remove 2 from the collection since the person's next greater height at this position has now been determined. Current collection: [0].

Is the height of the person at index 0 less than the current height of 14? Yes. We update the corresponding answer slot by using our collection of index values: ans[0] = 14. We now remove 0 from the collection since the person's next greater height at this position has now been determined. Current collection: [].

The collection is now empty so we have no previous heights to compare with the current height. We now add the current height's index value to the collection: [3].

Collection's index-to-height correspondence: [14]. Current answer array: [14, 12, 14, -1, -1].
413The current height is now 13. Are there any index values in the collection that represent a height less than 13? No. We now add the current height's index value to the collection: [3, 4].

Collection's index-to-height correspondence: [14, 13]. Current answer array: [14, 12, 14, -1, -1].

We have now finished processing the heights for all people. The final answer array is [14, 12, 14, -1, -1], as desired.

As before, it may be illustrative to show a condensed table where the reported next greater height for each person is included as well as what our reference collection of index values looks like after processing each person (along with the heights that correspond to these index values):

PersonHeightIndex collection after person processedIndex-height correspondenceAnswer array
012[0][12][-1, -1, -1, -1, -1]
111[0, 1][12, 11][-1, -1, -1, -1, -1]
212[0, 2][12, 12][-1, 12, -1, -1, -1]
314[3][14][14, 12, 14, -1, -1]
413[3, 4][14, 13][14, 12, 14, -1, -1]

The table above shows more clearly how the answer array is updated in conjunction with index values being removed from our collection; that is, for example, after person 2 was processed, we removed index 1 from our collection and updated the value at index 1 in the answer array to be equal to the height of the current person being processed, the next greater height for the person at index 1, namely the height of 12.

Code implementation

Now for the code implementation of the process described above:

def next_greater_height_2(heights):
height_collection = []
ans = [-1] * len(heights)

for i in range(len(heights)):
curr_height = heights[i]

# remove all index values in our collection that correspond to
# previously encountered heights less than the current height
# (and then update the answer array to point to the curren height as
# the next greater height for the people positioned at those index values)
while height_collection and heights[height_collection[-1]] < curr_height:
prev_height_index = height_collection.pop()
ans[prev_height_index] = curr_height

# add the index for the current person's height to the collection,
# which is guaranteed to correspond to a height less than all
# other correspondent heights in the index collection
height_collection.append(i)

return ans

Code implementation confirms process description

The code above closely follows the process described previously; in fact, if we add a simple print statement at the end of each for loop iteration (i.e., after each person has been processed), then we can see this more clearly for ourselves:

print(
f'Person: {i}; '
f'Height: {heights[i]}; '
f'Index collection: {index_collection}; '
f'Index-height correspondence: {[heights[i] for i in index_collection]}; '
f'Answer array: {ans}'
)

The console output then confirms the work we did previously (horizontal spacing adjustments added after printing):

Person: 0;  Height: 12;  Index collection: [0];     Index-height correspondence: [12];      Answer array: [-1, -1, -1, -1, -1]
Person: 1; Height: 11; Index collection: [0, 1]; Index-height correspondence: [12, 11]; Answer array: [-1, -1, -1, -1, -1]
Person: 2; Height: 12; Index collection: [0, 2]; Index-height correspondence: [12, 12]; Answer array: [-1, 12, -1, -1, -1]
Person: 3; Height: 14; Index collection: [3]; Index-height correspondence: [14]; Answer array: [14, 12, 14, -1, -1]
Person: 4; Height: 13; Index collection: [3, 4]; Index-height correspondence: [14, 13]; Answer array: [14, 12, 14, -1, -1]

Approach 3 (single pass, modified question)

Was all of the pain and suffering involved in hammering out the approach above worth it? Maybe. The truth is that many problems won't just be about what an element's next greater or smaller element is; instead, the problem will have something to do with how these elements relate to each other in some way.

Modifed problem statement

For example, for the "next greater height" problem we've been considering, what if the question were tweaked slightly to not be about what a height's next greater height is but how many spaces there are between people with these heights?

Modified solution

Consider again how the people are lined up:

Given the heights [12, 11, 12, 14, 13], we know from our previous work that each height's next greater height is given by [14, 12, 14, -1, -1], where -1 conveys there is no next greater height for the height of the person at that position. If the answer array is now comprised of values that denote how many spaces there are between the current person and the person with the next greater height, then our answer array becomes [3, 1, 1, 0, 0], where 0 conveys the person at that position does not have someone to their right with a greater height.

How is it possible to assemble this answer array? Do we have to significantly revise our previous solution approach(es)? No. In fact, the second approach above, where we used a collection of index values, gives us all we need because the positional information we need for each person is provided by the index values themselves:

  • Person 0: When we encounter the next greater height of 14, we note that this next greater height occurs at position or index 3 (i.e., heights[3] == 14). The current height of 12 for person 0 occurs at position or index 0 (here we can take advantage of the fact that the numeric label for each person corresponds to the index value of the corresponding height; that is, person x will have height heights[x]). We can use the difference in index values to compute how many spaces there are between these people: 3 - 0 = 3.
  • Person 1: Current height of 11 occurs at index 1 and next greater height of 12 occurs at index 2. The number of spaces between these people: 2 - 1 = 1.
  • Person 2: Current height of 12 occurs at index 2 and next greater height of 14 occurs at index 3. The number of spaces between these people: 3 - 2 = 1.
  • Person 3: Current height of 14 occurs at index 3 and there is no next greater height; hence, report 0.
  • Person 4: Current height of 13 occurs at index 4 and there is no next greater height; hence, report 0.

That's it. That's all there is to do. The code modifications required, hightlighted below, are quite minor:

Approach 3 (spaces between people)
def next_greater_height_3(heights):
index_collection = []
ans = [0] * len(heights)

for i in range(len(heights)):
curr_height = heights[i]
while index_collection and heights[index_collection[-1]] < curr_height:
prev_height_index = index_collection.pop()
spaces_between = i - prev_height_index
ans[prev_height_index] = spaces_between
index_collection.append(i)

return ans
Approach 2 (next greater height)
def next_greater_height_2(heights):
index_collection = []
ans = [-1] * len(heights)

for i in range(len(heights)):
curr_height = heights[i]
while index_collection and heights[index_collection[-1]] < curr_height:
prev_height_index = index_collection.pop()
ans[prev_height_index] = curr_height

index_collection.append(i)

return ans

LC 739. Daily Temperatures

Problem statement

Let's now turn our attention to LC 739. Daily Temperatures for some practice. Here's the problem statement for ease of reference:

Given an array of integers temperatures that represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

For example, if temperatures = [73,74,75,71,69,72,76,73] is given as input, then the desired output would be as follows: [1,1,4,2,1,1,0,0].

Solution

This is virtually the same problem as the modified question for the next greater height problem where we looked at the number of spaces between each person and the next person of greater height. The solution to this LeetCode problem is almost identical (except here we're dealing with temperatures instead of heights, of course):

class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
index_collection = []
answer = [0] * len(temperatures)

for i in range(len(temperatures)):
curr_temp = temperatures[i]
while index_collection and temperatures[index_collection[-1]] < curr_temp:
prev_temp_index = index_collection.pop()
days_between = i - prev_temp_index
answer[prev_temp_index] = days_between
index_collection.append(i)

return answer

Arguably the main challenge for this problem (and most other kinds of problems) is to actually identify that our solution approach is relevant and then to implement it without issues. That's often where the real difficulty lies.

Sliding window minimum

Let's try one last problem before bothering ourselves with technical terms and concepts: the sliding window minimum problem.

Problem statement

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return an answer array that contains the minimum value for each sliding window of size k.

For example, if the input array is nums = [11, 13, -11, -13, 15, 13, 16, 17] and k = 3, then the desired output or answer array would be [-11, -13, -13, -13, 13, 13]:

Window position                         Min ------------------------               ----- [11  13  -11] -13  15  13  16  17       -11  11 [13  -11  -13] 15  13  16  17       -13  11  13 [-11  -13  15] 13  16  17       -13  11  13  -11 [-13  15  13] 16  17       -13  11  13  -11  -13 [15  13  16] 17        13  11  13  -11  -13  15 [13  16  17]       13

False start

In the next greater height problem at the beginning of this post, we saw that it was an effective strategy to maintain a collection that we could use to reference previously encountered heights where the collection was comprised of either the heights themselves (Approach 1) or indexes that we could use to obtain the heights themselves (Approach 2). For both approaches, the collections we maintained effectively corresponded to heights that were weakly decreasing (i.e., values that were decreasing or possibly equivalent).

  • Approach 1: The height collections after processing people 4, 3, 2, 1, and 0 were as follows, respectively:

    • [13]
    • [14]
    • [14, 12]
    • [14, 12, 11]
    • [14, 12]
  • Approach 2: The index collections after processing people 0, 1, 2, 3, and 4 were as follows, respectively (height correspondence shown to the right):

    [0][12][0, 1][12, 11][0, 2][12, 12][3][14][3, 4][14, 13]{\small \begin{array}{lcl} \texttt{[0]} &\longrightarrow & \texttt{[12]}\\ \texttt{[0, 1]} &\longrightarrow & \texttt{[12, 11]}\\ \texttt{[0, 2]} &\longrightarrow & \texttt{[12, 12]}\\ \texttt{[3]} &\longrightarrow & \texttt{[14]}\\ \texttt{[3, 4]} &\longrightarrow & \texttt{[14, 13]} \end{array}}

As demonstrated above, the heights we could reference by means of these collections we were maintaining in both approaches were weakly decreasing (strictly decreasing in Approach 1 and weakly decreasing in Approach 2). Specifically, the heights in the collection progressed from largest to smallest and went from "oldest" to "newest"; that is, the leftmost height was encountered before any other heights that followed, and the "newest" height was always the current height we just encountered.

The last part in the sentence above bears repeating because it indicates how we actually go about maintaining the collection: the "newest" height was always the current height we just encountered. If the collection of heights is decreasing and the current height is always the newest height in the collection, then this means we need to keep removing heights from the collection until the current height is the smallest one. Doing so ensures we maintain the "collection is decreasing" invariant. For example, if our height collection is [18, 16, 14, 11, 8, 4] and we encounter a new height of 13, then we need to remove every element of the collection less than 13 before we add this "newest" current height: [18, 16, 14, 13].

How does all of this help for the current problem of finding the minimum value in each three-element sliding window as we move from left to right? Since we're interested in the minimum value for each window and the rightmost value in the collections we maintained previously was always the smallest value, maybe this means we could dynamically maintain a "window collection" where we always picked off the rightmost value as the minimum? Let's try (first recall our input array: nums = [11, 13, -11, -13, 15, 13, 16, 17]):

  • The first value is 11 with index 0. Right now our collection is empty and the window is not yet of size k = 3. Hence, we add 0 to our collection and proceed. Current collection: [0].

  • The second value is 13 with index 1. Our collection right now is [0] which corresponds to the value of 11. Oops. We've already run into a problem: what do we do with index 1 that corresponds to value 13? If we add it to the collection, then we'll actually need to remove what's currently in the collection to maintain the "collection is decreasing" invariant. Our collection would go from [0] to [1], which corresponds to the value of [13], and this respects the "decreasing invariant" of our collection. If we did not remove 0 from our collection before adding 1, then our collection would be [0, 1], which corresponds to values [11, 13], and that would violate the "decreasing invariant" of our collection.

    Simply removing index 0 from our collection is really not an option here. If the first three elements of the input array were, for example, [11, 13, 12], then removing the ability to reference 11 means we've actually lost the ability to accurately determine the minimum value for the first three-element window.

We need a different strategy. What if our collection referred to increasing values from left to right instead of decreasing values? Then the leftmost value would now be the smallest value (i.e., minimum) and we would not have to remove it whenever we encountered a larger value. Let's try again (input array for quick reference: nums = [11, 13, -11, -13, 15, 13, 16, 17]):

  • The first value is 11 with index 0. Right now our collection is empty and the window is not yet of size k = 3. Hence, we add 0 to our collection and proceed. Current collection: [0].
  • The second value is 13 with index 1. Our collection right now is [0] which corresponds to value [11]. Since 13 is greater than 11, we can simply add its index to our collection and proceed. Current collection: [0, 1].
  • The third value is -11 with index 2. Our collection right now is [0, 1] which corresponds to values [11, 13]. But we want our collection to be increasing, where each newly added index corresponds to the greatest value referenced in the collection. To accommodate the addition of -11 to our collection (while maintaining the "increasing invariant"), we need to remove all indexes from our collection that correspond to values smaller than -11, namely all indexes in this case since both 11 and 13 are greater than -11. Our new collection becomes [2] which corresponds to value [-11]. Also, since we've now encountered the third value, we now have a 3-element window, and its minimum is the leftmost value referenced by our collection (i.e., nums[2] == -11).

This strategy seems like it might work. Let's write things out in tabular form as we did with the previous approaches, where this time we'll have six columns (each row's column values will refer to the state of things after the current indexed value has been processed):

  • Index: This is the index of the value being processed.
  • Value: This is the value that corresponds to the row's index value.
  • Index collection: This is the increasing index collection (i.e., indexes correspond to values that increase from smaller to larger).
  • Index-value correspondence: Translation of indexes in the collection to their correspondent values (for ease of reference).
  • Window indexes: We're told that the window is of size k = 3 and moves one unit from left to right. Hence, the sliding window indexes are [0, 1, 2] for the first window, [1, 2, 3] for the second window, and so on. This should be useful as a sanity check to ensure we don't include as a window minimum a value that is not actually in the window!
  • Window minimum: This is the minimum value for the current window of size k = 3.

First recall our input: nums = [11, 13, -11, -13, 15, 13, 16, 17], k = 3. Now let's try to implement the strategy discussed above in tabular form:

IndexValueIndex collectionIndex-value correspondenceWindow indexesWindow minimum
011[0][11][0, x, x]
113[0, 1][11, 13][0, 1, x]
2-11[2][-11][0, 1, 2]-11
3-13[3][-13][1, 2, 3]-13
415[3, 4][-13, 15][2, 3, 4]-13
513[3, 5][-13, 13][3, 4, 5]-13
616[3, 5, 6][-13, 13, 16][4, 5, 6]-13

Oh no. The strategy seemed to be working great, but the last row above cannot be correct — the index of 3 in the index collection [3, 5, 6] is not valid when we encounter index 6 because the window of length k = 3 with index 6 as its right endpoint has the following indexes: [4, 5, 6]. We've included an invalid index!

Is the strategy we were working on implementing above in tabular form completely doomed? Do we need to pursue a different strategy altogether? Or can we make a slight adjustment to fix everything?

Fixed start

Fortunately, the exact issue of what went wrong in the last row above is easy to identify: the index collection we were maintaining has an index value that is invalid for the sliding window; that is, when our sliding window of length k = 3 ends at index 6, this means the sliding window extends across indexes [4, 5, 6]. The index 3 is thus invalid. What should we do? What if we just removed this invalid index from our collection? Would that work? If we removed only the invalid index, then our collection would become [5, 6], which would correspond to values [13, 16]. Does this work?

The sliding window that extends across indexes [4, 5, 6] corresponds to the following values: [15, 13, 16]; hence, the minimum value for this window is 13, which occurs at index 5. And this is now the leftmost value in our index collection since we only removed the invalid index! This isn't just a happy coincidence or chance.

Recall that for each new value we encounter, we ensure it is the largest value referred to in our index collection, where are our index collection represents corresponding values that increase. Furthermore, what's the largest size our index collection should ever possibly be? Answer: The size of the sliding window, k. Why? If the index collection were larger than the size of the sliding window itself, k = 3 in this case, then our collection would automatically have an invalid index. So how do we ensure the index collection never exceeds a size of k and only ever has valid indexes? The manner in which the sliding window moves is a hint.

Once the initial window size of k has been reached, every time the window shifts a single unit to the right, the window's previous leftmost index must be removed as a valid index from our index collection (if it is present); that is, if i is the index of the value we have currently processed to maintain our collection's increasing or decreasing invariant, and our sliding window is of size k, then the leftmost index that must be removed (if it is part of our collection) is i - k. For example, if i = 7, and k = 3, then the valid window indexes are [5, 6, 7], and the leftmost index of the previous window which is no longer valid and would need to be removed from our collection (if it was present) would be i - k = 7 - 3 = 4.

When can the scenario described above actually happen? This can happen when the index in need of removal corresponds to the minimum value for k windows of size k, and this is exactly what happened when we were progressing through the table above when we encountered our issue:

  • Indexes [1, 2, 3] corresponded to values [13, -11, -13]. Minimum: -13 (index 3).

  • Indexes [2, 3, 4] corresponded to values [-11, -13, 15]. Minimum: -13 (index 3).

  • Indexes [3, 4, 5] corresponded to values [-13, 15, 13]. Minimum: -13 (index 3).

  • Indexes [4, 5, 6] corresponded to values [15, 13, 16]. Minimum: 13, not -13 (index 5, not 3).

    The value nums[3] == -13 was the minimum value for k = 3 windows. This index value is no longer valid for this window because it was the leftmost index of the previous window.

How do we "just remove" the invalid index of 3 when our increasing index collection of [3, 5, 6] corresponds to values [-13, 13, 16] even though the sliding window only covers indexes [4, 5, 6] which corresponds to values [15, 13, 16]? In all of the approaches thus far, we have always added/removed values to/from our collection from the right in order to maintain the collection's increasing or decreasing invariant as well as the order in which we've encountered elements ("oldest" to "newest" from left to right, respectively). We are still doing that in this approach that we've been describing, but what's to stop us from removing invalid values in our collection from the left (when needed)?

Removing 3 from the left of [3, 5, 6] means we now have [5, 6] (correspondent values [13, 16]), which are valid window indexes for the window that extends across indexes [4, 5, 6]. Hence, removing an element from the left did not disturb the increasing invariant of our collection that we've been trying to maintain — we simply removed an invalid value. The reward is that the new leftmost index in our collection, 5, corresponds to the minimum value of the current three-element window: nums[5] == 13.

Let's try our tabular approach again, but this time we'll remove invalid indexes from the left of our collection if we encounter them before reporting a window minimum:

IndexValueIndex collectionIndex-value correspondenceWindow indexesIndex to remove (if present)Window minimum
011[0][11][0, x, x]
113[0, 1][11, 13][0, 1, x]
2-11[2][-11][0, 1, 2]-11
3-13[3][-13][1, 2, 3]3 - 3 = 0 != 3-13
415[3, 4][-13, 15][2, 3, 4]4 - 3 = 1 != 3-13
513[3, 5][-13, 13][3, 4, 5]5 - 3 = 2 != 3-13
616[5, 6][13, 16][4, 5, 6]6 - 3 = 3 == 3 (removed)13
717[5, 6, 7][13, 16, 17][5, 6, 7]7 - 3 = 4 != 513

If we collect the window minimums from the table above into an array, then we get [-11, -13, -13, -13, 13, 13], as desired.

Code implementation

Now for the code implementation of the process described above:

def sliding_window_min_1(nums, k):
index_collection = []
ans = []

for i in range(len(nums)):
curr_num = nums[i]

# remove all index values in our collection that correspond to
# previously encountered numbers greater than the current number
# (note that removals are made from the right)
while index_collection and nums[index_collection[-1]] > curr_num:
index_collection.pop()

# add the index for the current number to the collection,
# which is guaranteed to correspond to a number greater than all
# other correspondent numbers in the index collection;
# importantly, the leftmost index of the collection corresponds
# to the smallest number represented in the collection
# (note that additions are made to the right)
index_collection.append(i)

# if the leftmost index in our collection corresponds
# to the leftmost index of the previous window,
# then remove this index in the collection _from the left_
if index_collection[0] == i - k:
index_collection.pop(0)

# do not start adding window minimums to the answer array
# until our window has reached a size of k
if i >= k - 1:
ans.append(nums[index_collection[0]])

return ans

The highlighted lines above are meant to serve as warnings in a way. Why? The code above clearly provides the correct output and respects every detail of our process and strategy:

print(sliding_window_min_1([11, 13, -11, -13, 15, 13, 16, 17], 3))
# [-11, -13, -13, -13, 13, 13]

The reason why the lines above are highlighted in warning colors is because of the data structure we are using for our index_collection, namely a Python list or "dynamic array." Python lists are excellent if we're mostly adding or removing elements from the end (i.e., the right) because these operations are O(1)O(1) on average. We're executing such operations whenever we move to a new index and add it to the index_collection — we remove all indexes from the right of the collection until the only remaining indexes correspond to values less than or equal to the current value. But what if we then discover that the leftmost index in our collection is the leftmost index of the previous window and is therefore an invalid index? We remove this index in our collection from the left.

Removing elements in arrays from the left on a regular basis is not performant because each removal is O(n)O(n), where nn represents the number of elements in the array (all array elements need to be shifted in memory once the first element is deleted). It would be ideal if we could use a data structure that supported efficient additions/removals from the right and from the left. What we're looking for is the so-called double-ended queue or "deque" for short, and Python has just the thing in its collections module: collections.deque:

class collections.deque([iterable[, maxlen]])

Returns a new deque object initialized left-to-right (using append()) with data from iterable. If iterable is not specified, the new deque is empty.

Deques are a generalization of stacks and queues (the name is pronounced "deck" and is short for "double-ended queue"). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1)O(1) performance in either direction.

Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n)O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

[...]

As noted on Stack Overflow and confirmed in CPython's source code, the deque in Python is implemented under the hood with a doubly-linked list. A comment on a separate Stack Overflow thread summarizes the takeaway rather neatly:

In my case, the time went down from 1:31 min. with pop(0) to 200 - 250 ms by using deque.

If we're going to be regularly adding and removing elements from the left and from the right, which is all we're actually doing with our index_collection in the solution above, then the data structure we should use is a double-ended queue. The code changes required, highlighted below, are minimal for the optimal solution:

# import the deque from the collections module in Python's standard library
from collections import deque

def sliding_window_min_2(nums, k):
# initialize empty deque for O(1) additions/removals from both ends
index_collection = deque()
ans = []

for i in range(len(nums)):
curr_num = nums[i]
while index_collection and nums[index_collection[-1]] > curr_num:
index_collection.pop()
index_collection.append(i)

if index_collection[0] == i - k:
# remove elements from the left in O(1) time
index_collection.popleft()

if i >= k - 1:
ans.append(nums[index_collection[0]])

return ans

It's worth noting that, until now with the advent of a double-ended queue for the optimal solution above, we have not explicitly mentioned using stacks or queues in any of our problem-solving approaches, much less "monotonic" stacks or queues. And that's because we haven't really needed to use that terminology — we used the ideas without knowing the names for these ideas. All of the terminology will soon be defined and made clear (once we wrap up this sliding window problem).

Code implementation confirms process description

The code above closely follows the process described previously; unfortunately, in this case, adding a print statement after each for loop (i.e., after each index has been processed) is not as simple as it was in the previous problem. Nonetheless, if you want to modify the solution code to accomplish this, then you can.

Modified solution code to print tabular values for each iteration
def sliding_window_min_2_print(nums, k):
index_collection = deque()
ans = []

for i in range(len(nums)):
removing_index = False
window_min_exists = False
curr_num = nums[i]
while index_collection and nums[index_collection[-1]] > curr_num:
index_collection.pop()
index_collection.append(i)

if index_collection[0] == i - k:
removing_index = True
removed_index = index_collection.popleft()

if i >= k - 1:
window_min_exists = True
window_min = nums[index_collection[0]]
ans.append(nums[index_collection[0]])

print(
f'Index: {i}; '
f'Value: {nums[i]}; '
f'Index collection: {list(index_collection)}; '
f'Index-value correspondence: {[nums[idx] for idx in index_collection]}; '
f'Window indexes: {[0, "x", "x"] if i == 0 else [0, 1, "x"] if i == 1 else [ val + (i - k) for val in range(1, k + 1)]}; '
f'Index to remove (if present): {i} - {k} = {i - k} {"==" if removing_index else "!="} {removed_index if removing_index else index_collection[0]} {"(removed)" if removing_index else ""}; '
f'Window minimum: {window_min if window_min_exists else ""}'
)

return ans

The console output then confirms the work we did previously (horizontal spacing adjustments added after printing):

Index: 0;  Value:  11;  Index collection: [0];        Index-value correspondence: [11];          Window indexes: [0, 'x', 'x'];   Index to remove (if present): 0 - 3 = -3 != 0;            Window minimum: 
Index: 1; Value: 13; Index collection: [0, 1]; Index-value correspondence: [11, 13]; Window indexes: [0, 1, 'x']; Index to remove (if present): 1 - 3 = -2 != 0; Window minimum:
Index: 2; Value: -11; Index collection: [2]; Index-value correspondence: [-11]; Window indexes: [0, 1, 2]; Index to remove (if present): 2 - 3 = -1 != 2; Window minimum: -11
Index: 3; Value: -13; Index collection: [3]; Index-value correspondence: [-13]; Window indexes: [1, 2, 3]; Index to remove (if present): 3 - 3 = 0 != 3; Window minimum: -13
Index: 4; Value: 15; Index collection: [3, 4]; Index-value correspondence: [-13, 15]; Window indexes: [2, 3, 4]; Index to remove (if present): 4 - 3 = 1 != 3; Window minimum: -13
Index: 5; Value: 13; Index collection: [3, 5]; Index-value correspondence: [-13, 13]; Window indexes: [3, 4, 5]; Index to remove (if present): 5 - 3 = 2 != 3; Window minimum: -13
Index: 6; Value: 16; Index collection: [5, 6]; Index-value correspondence: [13, 16]; Window indexes: [4, 5, 6]; Index to remove (if present): 6 - 3 = 3 == 3 (removed); Window minimum: 13
Index: 7; Value: 17; Index collection: [5, 6, 7]; Index-value correspondence: [13, 16, 17]; Window indexes: [5, 6, 7]; Index to remove (if present): 7 - 3 = 4 != 5; Window minimum: 13

LC 239. Sliding Window Maximum

Problem statement

Let's now turn our attention to LC 239. Sliding Window Maximum for some practice. Here's the problem statement for ease of reference:

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

For example, if nums = [1,3,-1,-3,5,3,6,7], k = 3 is given as input, then the desired output would be as follows: [3,3,5,5,6,7]. The following illustration can help us see this more clearly (just like we did for the sliding window minimum problem earlier):

Window position                Max ---------------               ----- [1  3  -1] -3  5  3  6  7       3  1 [3  -1  -3] 5  3  6  7       3  1  3 [-1  -3  5] 3  6  7       5  1  3  -1 [-3  5  3] 6  7       5  1  3  -1  -3 [5  3  6] 7       6  1  3  -1  -3  5 [3  6  7]      7

Solution

The problem above is virtually identical to the sliding window minimum problem we worked so hard to solve. In fact, the only difference is that now we're looking for the maximum of each window instead of the minimum. This means the index_collection we maintain should be decreasing (so that the leftmost value will always be a maximum). The rest of the logic stays the exact same. Hence, the only thing we need to do is change the comparison in the while loop from > to <; that is, we need to change

while index_collection and nums[index_collection[-1]] > curr_num:

to

while index_collection and nums[index_collection[-1]] < curr_num:

Everything else stays as it was in our original solution:

class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
index_collection = deque()
ans = []

for i in range(len(nums)):
curr_num = nums[i]
while index_collection and nums[index_collection[-1]] < curr_num:
index_collection.pop()
index_collection.append(i)

if index_collection[0] == i - k:
index_collection.popleft()

if i >= k - 1:
ans.append(nums[index_collection[0]])

return ans

Interestingly, we can actually get away with not using a deque here (i.e., we just use a list instead and left removals cost more computationally than they might otherwise). The answer is still accepted by LeetCode even though it's notably slower than the solution using a deque. The test cases LeetCode uses are not public/visible, but presumably the reason the list-based solution is still acceptable is because most operations on index_collection are additions and removals from the right, where these list operations are still O(1)O(1). Only on certain occasions do we need to remove an element from the left, which will be O(k)O(k) instead of O(1)O(1) since the largest size of the index collection we're maintaining is of size kk.

We should note that the performance concern remarked on above (i.e., O(k)O(k) left-removals instead of O(1)O(1)) pales in comparison to the most significant computational gains of crafting a solution that performs in O(n)O(n) with a single pass instead of processing every single subarray on its own in a brute force fashion, which would be O(n2)O(n^2). That kind of solution would definitely not be accepted for this hard problem.

List-based solution to LC 239 that is less performant than deque-based solution but accepted nonetheless
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
index_collection = []
ans = []

for i in range(len(nums)):
curr_num = nums[i]
while index_collection and nums[index_collection[-1]] < curr_num:
index_collection.pop()
index_collection.append(i)

if index_collection[0] == i - k:
index_collection.pop(0)

if i >= k - 1:
ans.append(nums[index_collection[0]])

return ans

Monotonic stacks and queues (deques)

Definition of "monotonic"

Mathematical background (not necessary but still helpful)

The Wiki article on monotonic functions is surprisingly helpful. The relevant portions have been reproduced below (with slight adjustments).

A function ff defined on a subset of the real numbers with real values is said to be monotonic if and only if ff is either entirely non-increasing or entirely non-decreasing:

Image 1Image 2Image 3

A function is said to be monotonically increasing (also increasing or non-decreasing) if for all xx and yy such that xyx\leq y one has f(x)f(y)f(x)\leq f(y), so ff preserves the order (Figure 1). Likewise, a function is said to be monotonically decreasing (also decreasing or non-increasing) if, whenever xyx\leq y, then f(x)f(y)f(x)\geq f(y), so it reverses the order (Figure 2).

If the order \leq in the definition of monotonicity is replaced by the strict order <<, one obtains a stronger requirement. A function with this property is said to be strictly increasing (also increasing). Again, by inverting the order symbol, one finds a corresponding concept called strictly decreasing (also decreasing). A function with either property is called strictly monotone.

To avoid ambiguity, the terms weakly monotone, weakly increasing and weakly decreasing are often used to refer to non-strict monotonicity.

The terms "non-decreasing" and "non-increasing" should not be confused with the (much weaker) negative qualifications "not decreasing" and "not increasing". For example, the non-monotonic function shown in Figure 3 first falls, then rises, then falls again. It is therefore not decreasing and not increasing, but it is neither non-decreasing nor non-increasing.

Let's first provide a working definition of the word monotonic:

Mathematics. (of a function or sequence) either consistently increasing in value and never decreasing, or consistently decreasing in value and never increasing:

A monotonic sequence can either converge or diverge, but it can never oscillate.

In the context of programming, we're generally concerned with a collection or "sequence" of values (as opposed to a function). Whether or not the sequence is deemed monotonic depends on how the values relate to each other in progression from left to right:

  • Strictly decreasing (each value is less than all preceding values)
  • Weakly decreasing (each value is less than or equal to all preceding values)
  • Strictly increasing (each value is greater than all preceding values)
  • Weakly increasing (each value is greater than or equal to all preceding values)

Basic code examples are illustrative in clarifying these definitions:

Strictly decreasing
[14, 13, 12, 11, 8, 6]
Weakly decreasing
[14, 13, 13, 12, 12, 11, 8, 6]
Strictly increasing
[-13, 13, 16, 18, 21]
Weakly increasing
[-13, 13, 13, 16, 18, 18, 18, 21]

Important observations due to "monotonic" definition

Avoid this section at your own risk!

This section is, without question, the most important section in this entire post. The observations detailed below serve as the foundation for all subsequently solved problems as well as all templates. Take whatever time is necessary to grok these important observations!

There are several important observations worth noting that stem directly from the definitions illustrated above:

  • Unique or duplicate values: "Strictly decreasing" and "strictly increasing" are both strict (all values are unique) whereas their "weak" variants are not (adjacent values may be equal which means duplicate values are permitted). The following terms are equivalent (I personally use the strict/weak terminology because I find them to be clearer than their alternatives):

    Strictly increasing  =  increasing
    Weakly increasing = non-decreasing

    Strictly decreasing = decreasing
    Weakly decreasing = non-increasing
  • Alternate terminology for "weakly": Sometimes the terms non-decreasing and non-increasing are used instead of weakly increasing and weakly decreasing, respectively (as shown above). Unfortunately, while such terminology is technically accurate, it arguably obscures the important behavior being highlighted; that is, for a sequence like [1, 2, 2, 3], calling it "non-decreasing" arguably obscures what we actually want to highlight, namely that the collection is increasing except when adjacent values can be equal. Saying the collection is "weakly increasing" seems to be a better choice of words.

    It's also arguably clearer to use the words "strictly increasing" instead of just "increasing" so as to be completely unambiguous.

  • Minimum/maximum values: If a sequence is strictly decreasing or weakly decreasing, then the leftmost value represents the maximum value in the collection. Similarly, if a sequence is strictly increasing or weakly increasing, then the leftmost value represents the minimum value in the collection.

  • Monotonicity invariant: The definition for invariant is what it sounds like:

    Mathematics. a quantity or expression that is constant throughout a certain range of conditions.

    The idea of an invariant in computer science is effectively the same but slightly nuanced:

    In computer science, an invariant is a logical assertion that is always held to be true during a certain phase of execution of a computer program. For example, a loop invariant is a condition that is true at the beginning and the end of every iteration of a loop.

    How is the idea of an invariant relevant to our work with monotonic stacks and queues? Imagine adding 3 to the weakly increasing monotonic stack [0, 1, 1, 4] without first removing any elements: [0, 1, 1, 4, 3]. The weakly increasing monotonic stack we had previously is now just a stack because its special property of monotonicity has been violated. "Maintaining" a monotonic stack or deque really means maintaining its invariant: monotonicity. The (weakly) increasing/decreasing stack or deque should remain (weakly) increasing/decreasing whenever elements are added or removed.

  • Adding elements: As noted above, special care must be taken when adding values to a monotonic stack or deque to ensure its monotonicity invariant remains intact. Specifically, adding value x means first removing all other values that would cause the invariant to be broken should x be added to the stack or queue in its current state — only then should x be added. Since the collection of values being maintained is a stack or deque, additions generally happen from the right. (If we are using a double-ended queue, then it is conceivable that we could add elements from the left, but this is usually not the case.)

  • Removing elements: Adding values generally happens from the right. Removal of values, which typically precedes the addition of new values, also generally happens from the right. Why? Because values that would otherwise break the invariant are effectively popped from the top/right before adding the new value to the top/right. Consider the following examples that illustrate what elements must be removed to keep the invariant intact in order to accommodate the addition of the value 5:

    Strictly decreasing
    [12, 10, 9, 5, 3, 2, 1] # Before addition of 5
    [12, 10, 9, 5] # After addition of 5
    Weakly decreasing
    [12, 10, 10, 9, 5, 3, 1, 0] # Before addition of 5
    [12, 10, 10, 9, 5, 5] # After addition of 5
    Strictly increasing
    [0, 1, 3, 5, 6, 10, 11] # Before addition of 5
    [0, 1, 3, 5] # After addition of 5
    Weakly increasing
    [1, 2, 2, 3, 5, 7, 8, 10] # Before addition of 5
    [1, 2, 2, 3, 5, 5] # After addition of 5

    It's clear visually from above that values are being removed from the right in order to accommodate the addition of the new value 5.

  • Removing elements from the left (when a queue-like operation is needed): In some cases (e.g., sliding windows), we may want to remove an element in our collection from the left. As illustrated previously, our collection's invariant is maintained with stack-like operations, namely popping old values from the top before pushing a new value to the top. This means values in our collection progress left to right from "oldest" to "newest" in terms of the recency in which each value was added.

    For sliding window problems especially, window values are generally added as the right endpoint advances and removed as the left endpoint advances. Since the leftmost values in our collection are always the "oldest", it makes sense that in certain scenarios we might want to remove the leftmost value. For example, suppose we have the strictly increasing collection [2, 4, 6] that represents the values of the following sliding window:

    12, 4, [2, 4, 7, 6], 8, 10

    What happens to our collection once the left boundary of the window advances? It's clear that 2 is no longer a valid value, and we must remove it from our collection.

    But stacks are not optimized for removing elements from the left. This is why double-ended queues (i.e., deques) are needed for some problems: the right end permits the stack-like push and pop operations for maintaining the (weakly) increasing/decreasing monotonicity invariant while the left end permits the queue-like operation of popping elements from the left. Note that the invariant is always left intact when elements are removed.

  • Next larger/smaller (or equal) value: See again the examples above for what elements must be removed in order to accommodate the addition of the 5 and what this means for each removed element's next larger or smaller value (first recall that elements in the collection progress left to right from "oldest" to "newest" in terms of the recency in which they were added to the collection):

    Monotonic invariant for collectionAdded 5's relation to removed elementsExplanation
    Strictly decreasingLarger than or equalThe original value collection [12, 10, 9, 5, 3, 2, 1] is transformed to [12, 10, 9] before the addition of 5; hence, the following values are removed (in this order): 1, 2, 3, 5. Each value removed is less than or equal to the newly added value of 5. This means that the removed values 1, 2, 3, 5 all have 5 as their next "larger than or equal" value.
    Weakly decreasingLarger thanThe original value collection [12, 10, 10, 9, 5, 3, 1, 0] is transformed to [12, 10, 10, 9, 5] before the addition of 5; hence, the following values are removed (in this order): 0, 1, 3. Each value removed is less than the newly added value of 5. This means that the removed values 0, 1, 3 all have 5 as their next "larger than" value.
    Strictly increasingSmaller than or equalThe original value collection [0, 1, 3, 5, 6, 10, 11] is transformed to [0, 1, 3] before the addition of 5; hence, the following values are removed (in this order): 11, 10, 6, 5. Each value removed is greater than or equal to the newly added value of 5. This means that the removed values 11, 10, 6, 5 all have 5 as their next "smaller than or equal" value.
    Weakly increasingSmaller thanThe original value collection [1, 2, 2, 3, 5, 7, 8, 10] is transformed to [1, 2, 2, 3, 5] before the addition of 5; hence, the following values are removed (in this order): 10, 8, 7. Each value removed is greater than the newly added value of 5. This means that the removed values 10, 8, 7 all have 5 as their next "smaller than" value.

    As all of the examples above indicate, if B is the value being added to the collection, then every value A popped from the collection has B as their next "larger/smaller (or equal)" value, where the larger/smaller (or equal) determination completely depends on what kind of monotonic invariant is being maintained for the collection.

    Furthermore, once every element in an input array has been iterated over, all remaining elements in the collection are those which had no such next larger/smaller (or equal) value based on the monotonic invariant being maintained for the collection. For example, if strictly increasing is the monotonic invariant being maintained, then, once the input array has been fully iterated over, all remaining elements in the collection have no next "smaller than or equal" value.

  • Previous larger/smaller (or equal) value: This is a bit harder to conceptualize at first, but it's worth it. In the "next larger/smaller (or equal) value" bullet point above, we were effectively trying to determine how 5 related to each element removed from the collection; that is, the value 5 was each removed element's "next larger/smaller (or equal)" value.

    If, however, we think about what happens when we stop removing elements, then we have actually obtained some useful information about a value previous to the 5 that we're trying to add to the collection. Since our collection holds values from "oldest" to "newest" (left to right), once we stop removing elements from the collection, the rightmost element still in the collection is actually 5's "previous larger/smaller (or equal)" value, where the larger/smaller (or equal) determination again depends on what kind of monotonic invariant is being maintained for the collection. If the collection happens to be empty once we stop removing elements before adding 5, then 5 has no "previous larger/smaller (or equal)" value. A table of examples will aid a great deal in clarification:

    Monotonic invariant for collectionRelation of rightmost element still in collection to added 5Explanation
    Strictly decreasingPrevious largerThe original value collection [12, 10, 9, 5, 3, 2, 1] is transformed to [12, 10, 9] before the addition of 5. The rightmost value still in the collection is 9. This means that 9 is 5's "previous larger" value.
    Weakly decreasingPrevious larger or equalThe original value collection [12, 10, 10, 9, 5, 3, 1, 0] is transformed to [12, 10, 10, 9, 5] before the addition of 5. The rightmost value still in the collection is 5. This means that 5 is 5's "previous larger or equal" value.
    Strictly increasingPrevious smallerThe original value collection [0, 1, 3, 5, 6, 10, 11] is transformed to [0, 1, 3] before the addition of 5. The rightmost value still in the collection is 3. This means that 3 is 5's "previous smaller" value.
    Weakly increasingPrevious smaller or equalThe original value collection [1, 2, 2, 3, 5, 7, 8, 10] is transformed to [1, 2, 2, 3, 5] before the addition of 5. The rightmost value still in the collection is 5. This means that 5 is 5's "previous smaller or equal" value.

    As all of the examples above indicate, if A is the value being added to the collection, then the rightmost value B still in the collection after all removals have taken place (if it exists) is A's "previous larger/smaller (or equal)" value, where the larger/smaller (or equal) determination completely depends on what kind of monotonic invariant is being maintained for the collection (there is no such previous value for A if all elements of the collection have been removed before adding A).

    For example, suppose we're given the following array of numbers (indexes drawn above array values for the sake of clarity):

             0  1  2  3  4  5  6  7  8   9
    nums = [ 8, 4, 5, 5, 6, 9, 9, 7, 10, 3 ]

    If we are maintaining a monotonic collection that is weakly decreasing, then our collection will be [8, 6] by the time we reach index 5. Since our collection is weakly decreasing, we must remove both of the elements currently in the collection before we can add the 9. Thus, there is no rightmost value in the collection once we remove these elements before adding the 9. This means that the 9 at index 5 has no "previous larger or equal" value.

    • What happens for the value at the next index? The value at index 6 is 9. Since our collection is weakly decreasing, and our current collection is [9], this means we do not need to remove any elements to maintain the monotonic invariant. The rightmost element in the collection before adding the current element is 9, and this means that the 9 at index 6 has 9 as its "previous larger or equal" value. Our collection then becomes [9, 9] once we add the current value of 9.
    • For the value of 7 at index 7, we do not need to remove any elements from the collection. The current collection's rightmost element is 9, which means the 7 at index 7 has 9 as its "previous larger or equal" value. Add 7 to the collection, which gives us [9, 9, 7] as the current collection.
    • For the value of 10 at index 8, we must remove all elements of the collection before we can add the 10, which means the 10 at index 8 has no "previous larger or equal" value.

    And so on. For each number encountered, we immediately determine that number's "previous value" by first popping all elements from the collection that would break the collection's monotonic invariant. The rightmost element remaining in the collection, if there is one, is the current element's "previous value"; otherwise, if the collection is empty, the current element has no such "previous value", as demonstrated above.

  • Previous AND next larger/smaller (or equal) values: Take a closer look at the tables from the two bullet points above. Note how "next" and "previous" values are obtained in relation to the current element we're about to add to the collection:

    • Next values: Each value removed from the collection has the current element we're trying to add to the collection as its next larger/smaller (or equal) value.

    • Previous values: We cannot add the current element to the collection until all values have been removed from the collection that would otherwise cause the collection's monotonic invariant to be broken with the addition of the current element.

      Once the removals from the collection have taken place, and before adding the current element to the collection, we note that the current element's previous larger/smaller (or equal) value is the rightmost value remaining in the collection (if there is one). If no values remain in the collection after the removals above, then the current element has no previous larger/smaller (or equal) value.

    The key observation is that both "next" and "previous" value determinations above can be made while processing the same element; that is, "next" values are determined first while elements are being removed from the collection, and then the current element's "previous" value is determined second by checking whether or not the collection still has any values, specifically the rightmost value, after all the removals. These determinations are made in sequence before adding the current element to the collection.

    The takeaway is that we get both pieces of information above without any extra computational work. Determining each element's "next" value in some comparative capacity is often how monotonic stacks are used to solve various problems, but what we've noticed above is that, if it's relevant to solving the given problem, then we can also obtain information about each element's "previous" value at no extra cost. The following table, which combines the examples from the previous two tables, makes all of this more concrete:

    Monotonic invariantNEXT value relation of removed elements to added elementPREVIOUS value relation to added elementExplanation
    Strictly decreasingLarger than or equalLarger thanThe original value collection [12, 10, 9, 5, 3, 2, 1] is transformed to [12, 10, 9] before the addition of 5; hence, the following values are removed (in this order): 1, 2, 3, 5. Each value removed is smaller than or equal to the newly added value of 5. This means that the removed values 1, 2, 3, 5 all have 5 as their next "larger than or equal" value.

    Before adding 5 to the updated collection [12, 10, 9], note that the collection's rightmost element is 9, which means 9 is 5's previous "larger than" value. We finally add 5 to the collection.
    Weakly decreasingLarger thanLarger than or equalThe original value collection [12, 10, 10, 9, 5, 3, 1, 0] is transformed to [12, 10, 10, 9, 5] before the addition of 5; hence, the following values are removed (in this order): 0, 1, 3. Each value removed is smaller than the newly added value of 5. This means that the removed values 0, 1, 3 all have 5 as their next "larger than" value.

    Before adding 5 to the updated collection [12, 10, 10, 9, 5], note that the collection's rightmost element is 5, which means 5 is 5's previous "larger than or equal" value. We finally add 5 to the collection.
    Strictly increasingSmaller than or equalSmaller thanThe original value collection [0, 1, 3, 5, 6, 10, 11] is transformed to [0, 1, 3] before the addition of 5; hence, the following values are removed (in this order): 11, 10, 6, 5. Each value removed is larger than or equal to the newly added value of 5. This means that the removed values 11, 10, 6, 5 all have 5 as their next "smaller than or equal" value.

    Before adding 5 to the updated collection [0, 1, 3], note that the collection's rightmost element is 3, which means 3 is 5's previous "smaller than" value. We finally add 5 to the collection.
    Weakly increasingSmaller thanSmaller than or equalThe original value collection [1, 2, 2, 3, 5, 7, 8, 10] is transformed to [1, 2, 2, 3, 5] before the addition of 5; hence, the following values are removed (in this order): 10, 8, 7. Each value removed is larger than the newly added value of 5. This means that the removed values 10, 8, 7 all have 5 as their next "smaller than" value.

    Before adding 5 to the updated collection [1, 2, 2, 3, 5], note that the collection's rightmost element is 5, which means 5 is 5's previous "smaller than or equal" value. We finally add 5 to the collection.

The table above hints at the fact that, after only a single pass, we can completely process an array of numbers to determine the following depending on which monotonic invariant is being maintained for our collection:

  • (strictly decreasing) each number's previous larger value as well as its next larger than or equal value

    This effectively allows us to determine over what range of values the current number can be considered a maximum (just exclude the number's previous larger value as well as its next larger than or equal value from the range — then the current number must be the largest value in the range).

  • (weakly decreasing) each number's previous larger or equal value as well as its next larger value

    This also effectively allows us to determine over what range of values the current number can be considered a maximum (just exclude the number's previous larger or equal value as well as its next larger value from the range — then the current number must be the largest value in the range).

  • (strictly increasing) each number's previous smaller value as well as its next smaller than or equal value

    This effectively allows us to determine over what range of values the current number can be considered a minimum (just exclude the number's previous smaller value as well as its next smaller than or equal value from the range — then the current number must be the smallest value in the range).

  • (weakly increasing) each number's previous smaller or equal value as well as its next smaller value

    This also effectively allows us to determine over what range of values the current number can be considered a minimum (just exclude the number's previous smaller or equal value as well as its next smaller value from the range — then the current number must be the smallest value in the range).

The insights from the bulleted points above are largely responsible for how we can come up with the optimal solutions to LC 907. Sum of Subarray Minimums and LC 2104. Sum of Subarray Ranges, two problems that would otherwise be exceedingly difficult to solve efficiently. These problems are remarked on in great detail in this post's epilogue, but solutions directly based on the comments above are included as "Approach 2" for each problem in the solved practice problems section.

Monotonic stack definition

Observations are much more important than definitions

The important observations discussed previously are far more important than the simple definitions that follow.

A monotonic stack is a stack whose values demonstrate monotonicity in some capacity: strictly decreasing, weakly decreasing, strictly increasing, or weakly increasing. The following are all examples of monotonic stacks (with an illustration of how monotonicity is maintained when a new value, 5, is added):

Monotonic stack (strictly decreasing)
[12, 10, 9, 5, 3, 2, 1] # Before addition of 5
[12, 10, 9, 5] # After addition of 5
Monotonic stack (weakly decreasing)
[12, 10, 10, 9, 5, 3, 1, 0] # Before addition of 5
[12, 10, 10, 9, 5, 5] # After addition of 5
Monotonic stack (strictly increasing)
[0, 1, 3, 5, 6, 10, 11] # Before addition of 5
[0, 1, 3, 5] # After addition of 5
Monotonic stack (weakly increasing)
[1, 2, 2, 3, 5, 7, 8, 10] # Before addition of 5
[1, 2, 2, 3, 5, 5] # After addition of 5

What defines the stack, however, is its interface, namely pushing and popping values from the right.

Monotonic queue (deque) definition

Observations are much more important than definitions

The important observations discussed previously are far more important than the simple definitions that follow.

A monotonic queue is really a double-ended queue or deque whose values demonstrate monotonicity in some capacity: strictly decreasing, weakly decreasing, strictly increasing, or weakly increasing. The following are all examples of monotonic deques (with an illustration of how monotonicity is maintained when a new value, 5, is added):

Monotonic deque (strictly decreasing)
[12, 10, 9, 5, 3, 2, 1] # Before addition of 5
[12, 10, 9, 5] # After addition of 5
Monotonic deque (weakly decreasing)
[12, 10, 10, 9, 5, 3, 1, 0] # Before addition of 5
[12, 10, 10, 9, 5, 5] # After addition of 5
Monotonic deque (strictly increasing)
[0, 1, 3, 5, 6, 10, 11] # Before addition of 5
[0, 1, 3, 5] # After addition of 5
Monotonic deque (weakly increasing)
[1, 2, 2, 3, 5, 7, 8, 10] # Before addition of 5
[1, 2, 2, 3, 5, 5] # After addition of 5

What defines the queue, however, is its interface, namely pushing new elements to the right and popping old elements from the left. The illustrations above clearly show collections of values where all old values are popped from the right, not from the left. This means the popping and pushing of values illustrated above are fundamentally stack-like in nature.

This is why the label of "monotonic queue" is a misnomer — it's misleading. We only claim to use a monotonic queue when removing elements from the left is necessary. In such cases, we use a double-ended queue or deque because the right end still needs the stack-like operations to maintain the invariant while the left end needs the queue-like operation of efficiently removing an element(s) from the left. Hence, it would be more accurate to call a monotonic queue a monotonic deque.

Common use cases for monotonic stacks and deques

Monotonic stacks and deques can crop up in unexpected ways and places, but the following are some conventional areas where these structures shine:

  • efficiently adding or removing values to a sorted collection of values while maintaining the sorted order
  • efficiently accessing a value's next larger/smaller (or equal) value
  • efficiently accessing a value's previous larger/smaller (or equal) value
  • efficiently accessing the maximum or minimum value of a contiguous subarray or sliding window

A simple stack (or list in Python) is sufficient for the first three points above, but a deque is needed for the last point. In general, deques are needed in the following circumstances:

  • sliding window problems where efficient access to the maximum or minimum is important
  • there's a bidirectional nature to the problem where values need to be processed in the order they appear and removed when no longer relevant
  • old values need to be discarded as new values are processed
  • insertion of new values causes invalidation of previously stored values (the deque allows efficient insertion of new values from the right and efficient removal of invalidated values from the left)

Monotonic deques can be used for more than just contiguous subarray or sliding window problems where access to the maximum or minimum is needed, but these are clearly situations where all of the points above apply and the use of a deque is warranted. Monotonic stacks can be used for everything else when removals from the left are not needed (e.g., next/previous larger/smaller (or equal) value, largest area or volume problems, stock span problems, etc.). A general safe rule of thumb to follow:

Start with a stack and only move to a deque if you realize you need to remove elements from the left for some reason.

The next few sections are devoted to probably two of the most common use cases for monotonic stacks: given an array of values, identify each value's next/previous larger/smaller (or equal) value (or indicate with -1 if it does not exist). The "next" and "previous" value problems can essentially be solved by means of two templates (one for the "next" value problems and one for the "previous" value problems), where only the comparison operator used to maintain the stack invariant dictates what kinds of values we can expect. Also, as alluded to in the important observations section, we can determine "next" and "previous" values in one pass — this approach is also covered below (after considering "next" and "previous" value determinations separately).

Templates for finding an element's "next" or "previous" value based on monotonic invariant being maintained

tip

The templates below will likely be much easier to understand if you first read the following bullet points in the important observations section, respectively:

  • "Next greater/smaller (or equal) value"
  • "Previous greater/smaller (or equal) value"
  • "Previous AND next larger/smaller (or equal) values"
Memorization suggestion
caution

If you're thoroughly familiar with the structure and rationale of the templates below and your while loop conditional for maintaining the stack invariant is always written in the flavor

while stack and nums[stack[-1]] ? curr_val:

where nums[stack[-1]] appears on the left of the comparison nums[stack[-1]] ? curr_val, then the tables below present easy ways to remember what kinds of values you can expect in your answer array based on what kind of comparison is being used to maintain the stack invariant.

NEXT value (flipped phonetic comparison operator):

NEXT values obtainedPhonetic comparsionComparison operator for maintaining stack (flipped)
Next larger><
Next larger or equal to>=<=
Next smaller<>
Next smaller or equal to<=>=

PREVIOUS value (negated phonetic comparison operator):

PREVIOUS values obtainedPhonetic comparsionComparison operator for maintaining stack (negated)
Previous larger><=
Previous larger or equal to>=<
Previous smaller<>=
Previous smaller or equal to<=>
Next value template
def fn_next(nums):
n = len(nums)
ans = [None] * n
stack = [] # monotonic stack
for i in range(n):
val_B = nums[i]
# the comparison operator (?) dictates what A's next value B represents
# (<) next larger value (weakly decreasing stack)
# (<=) next larger or equal value (strictly decreasing stack)
# (>) next smaller value (weakly increasing stack)
# (>=) next smaller or equal value (strictly increasing stack)
while stack and nums[stack[-1]] ? val_B:
idx_val_A = stack.pop()
ans[idx_val_A] = val_B
stack.append(i)

# process elements that never had a "next" value that satisfied the criteria
while stack:
idx_val_A = stack.pop()
ans[idx_val_A] = -1

return ans
Previous value template
def fn_previous(nums):
n = len(nums)
ans = [None] * n
stack = [] # monotonic stack
for i in range(n):
val_A = nums[i]
# the comparison operator (?) dictates what A's previous value B represents
# (<=) previous larger (strictly decreasing)
# (<) previous larger or equal value (weakly decreasing)
# (>=) previous smaller value (strictly increasing)
# (>) previous smaller or equal value (weakly increasing)
while stack and nums[stack[-1]] ? val_A:
stack.pop()

if stack:
idx_val_B = stack[-1]
val_B = nums[idx_val_B]
ans[i] = val_B
else:
ans[i] = -1

stack.append(i)

return ans
Combined templates for previous and next values
def fn(nums):
n = len(nums)
ans = [[-1, -1] for _ in range(n)] # default values for missing PREVIOUS and NEXT values, respectively
stack = [] # monotonic stack

# the comparison operator (?) dictates what each element's PREVIOUS and NEXT values will be
# (<=) PREVIOUS larger value and NEXT larger or equal value (strictly decreasing stack)
# (<) PREVIOUS larger or equal value and NEXT larger value (weakly decreasing stack)
# (>=) PREVIOUS smaller value and NEXT smaller or equal value (strictly increasing stack)
# (>) PREVIOUS smaller or equal value and NEXT smaller value (weakly increasing stack)
for i in range(n):
while stack and nums[stack[-1]] ? nums[i]:
# NEXT values processed
idx = stack.pop()
ans[idx][1] = i # use nums[i] instead of i to directly record array values instead of indexes
# PREVIOUS values processed
ans[i][0] = -1 if not stack else stack[-1] # use nums[stack[-1]] instead of stack[-1]
# to directly record array values instead of indexes
stack.append(i)

return ans

It's most important to become very familiar with the structure of each template above (i.e., why things are structured the way they are). Remembering which comparison operator corresponds to which kind of monotonic stack being maintained, and thus what kind of criteria-satisfying value we're searching for, is much less important: this can easily be attained by providing yourself with a sample stack of values and asking yourself what you would need to do if you tried inserting a new value into the stack (make it concrete by giving yourself a monotonic stack with a few elements and then trying to insert another element). Answering your own question in this way will tell you what kind of comparison needs to be made to find the values you're searching for, but none of this will help unless you know the structure for maintaining the stack.

The following three sections separately consider each problem that leads to each template above.

Common problem (with template): Find a value's "next" larger/smaller (or equal) value

Monotonic stacks below contain index values

Monotonic stacks will very often not contain the input array's values themselves but the indexes which point to these values. This makes it possible for us to not only get access to the array values themselves but also to positional information about where the array values reside. This can be confusing at first though if you are only used to seeing monotonic stacks that directly use array values.

Consult the template and/or tabular summary as reference points

The next value template and/or next value "tabular summary", which appear after the provided solutions/approaches to the questions posed in the bulleted list below, can be quite helpful to use as reference points while working through the various approaches.

One of the most common use cases for a monotonic stack is to determine each value's "next" larger/smaller (or equal) value (i.e., the value that comes to the right of a given value that meets the desired criteria):

  • Next larger value: Given value A, what is the next value B such that A < B?
  • Next larger or equal value: Given value A, what is the next value B such that A <= B?
  • Next smaller value: Given value A, what is the next value B such that A > B?
  • Next smaller or equal value: Given value A, what is the next value B such that A >= B?

Note that the value B referred to above will always be in reference to the current value being processed since we will be processing the values from left to right (the monotonic stack will always be comprised of previous elements we've encountered, oldest to newest, left to right, whose next value that meets the criteria is the current value we are considering). To illustrate this more clearly, each problem variation in the bulleted list above is solved below where the roles of "values A and B" have been explicitly designated in each solution (i.e., value B always refers to value A's next value that meets the specified criteria).

The following array of numbers will be used as input in each solution approach for the sake of clarity and consistency:

nums = [14, 17, 13, 14, 14, 19, 12, 14, 18]

Values that ultimately end up having no next value that satisfies the specified criteria will report a "next value" of -1 in the answer array to communicate this. The answer array, ans, is always initialized to the length of the input array and filled with None values. This is done to concretely show how every element is processed (i.e., as opposed to initializing the answer array with -1 and then not processing values that never have a next value that satisfies the criteria).

Next larger value

def fn(nums):
n = len(nums)
ans = [None] * n
dec_stack = [] # monotonic stack (weakly decreasing)
for i in range(n):
val_B = nums[i]
while dec_stack and nums[dec_stack[-1]] < val_B:
idx_val_A = dec_stack.pop()
ans[idx_val_A] = val_B
dec_stack.append(i)

# process elements that never had a next larger value
while dec_stack:
idx_val_A = dec_stack.pop()
ans[idx_val_A] = -1

return ans

nums = [14, 17, 13, 14, 14, 19, 12, 14, 18]
print(fn(nums)) # [17, 19, 14, 19, 19, -1, 14, 18, -1]
Intuition

The current value being processed, val_B, is always the next value in relation to whatever values are in the stack (since the stack is comprised of values encountered before the current value); hence, for another value, val_A, to have val_B as its next larger value, the value val_A will need to be popped from the stack, and it will need to be smaller than (<) the current value, val_B.

Maintaining a weakly decreasing monotonic stack is perfectly suited for solving this problem. To see why, consider what would need to happen if we tried adding 5 to the following stack: [8, 6, 5, 4, 4].

  • Is 4 less than 5? Yes. Pop 4 from the stack, and note that 4's next larger value is 5. Stack's new state: [8, 6, 5, 4].
  • Is 4 less than 5? Yes. Pop 4 from the stack, and note that 4's next larger value is 5. Stack's new state: [8, 6, 5].
  • Is 5 less than 5? No. Push 5 to the stack. Stack's new state: [8, 6, 5, 5]. Continue to next element.

This is how each "next larger value" is determined.

Next larger or equal value

def fn(nums):
n = len(nums)
ans = [None] * n
dec_stack = [] # monotonic stack (strictly decreasing)
for i in range(n):
val_B = nums[i]
while dec_stack and nums[dec_stack[-1]] <= val_B:
idx_val_A = dec_stack.pop()
ans[idx_val_A] = val_B
dec_stack.append(i)

# process elements that never had a next larger or equal value
while dec_stack:
idx_val_A = dec_stack.pop()
ans[idx_val_A] = -1

return ans

nums = [14, 17, 13, 14, 14, 19, 12, 14, 18]
print(fn(nums)) # [17, 19, 14, 14, 19, -1, 14, 18, -1]
Intuition

The current value being processed, val_B, is always the next value in relation to whatever values are in the stack (since the stack is comprised of values encountered before the current value); hence, for another value, val_A, to have val_B as its next larger or equal value, the value val_A will need to be popped from the stack, and it will need to be smaller than or equal (<=) to the current value, val_B.

Maintaining a strictly decreasing monotonic stack is perfectly suited for solving this problem. To see why, consider what would need to happen if we tried adding 5 to the following stack: [8, 6, 5, 4].

  • Is 4 less than or equal to 5? Yes. Pop 4 from the stack, and note that 4's next larger or equal value is 5. Stack's new state: [8, 6, 5].
  • Is 5 less than or equal to 5? Yes. Pop 5 from the stack, and note that 5's next larger or equal value is 5. Stack's new state: [8, 6].
  • Is 6 less than or equal to 5? No. Push 5 to the stack. Stack's new state: [8, 6, 5]. Continue to next element.

This is how each "next larger or equal value" is determined.

Next smaller value

def fn(nums):
n = len(nums)
ans = [None] * n
inc_stack = [] # monotonic stack (weakly increasing)
for i in range(n):
val_B = nums[i]
while inc_stack and nums[inc_stack[-1]] > val_B:
idx_val_A = inc_stack.pop()
ans[idx_val_A] = val_B
inc_stack.append(i)

# process elements that never had a next smaller value
while inc_stack:
idx_val_A = inc_stack.pop()
ans[idx_val_A] = -1

return ans

nums = [14, 17, 13, 14, 14, 19, 12, 14, 18]
print(fn(nums)) # [13, 13, 12, 12, 12, 12, -1, -1, -1]
Intuition

The current value being processed, val_B, is always the next value in relation to whatever values are in the stack (since the stack is comprised of values encountered before the current value); hence, for another value, val_A, to have val_B as its next smaller value, the value val_A will need to be popped from the stack, and it will need to be larger than (>) the current value, val_B.

Maintaining a weakly increasing monotonic stack is perfectly suited for solving this problem. To see why, consider what would need to happen if we tried adding 8 to the following stack: [3, 4, 8, 9, 9].

  • Is 9 greater than 8? Yes. Pop 9 from the stack, and note that 9's next smaller value is 8. Stack's new state: [3, 4, 8, 9].
  • Is 9 greater than 8? Yes. Pop 9 from the stack, and note that 9's next smaller value is 8. Stack's new state: [3, 4, 8].
  • Is 8 less than 8? No. Push 8 to the stack. Stack's new state: [3, 4, 8, 8]. Continue to next element.

This is how each "next smaller value" is determined.

Next smaller or equal value

def fn(nums):
n = len(nums)
ans = [None] * n
inc_stack = [] # monotonic stack (strictly increasing)
for i in range(n):
val_B = nums[i]
while inc_stack and nums[inc_stack[-1]] >= val_B:
idx_val_A = inc_stack.pop()
ans[idx_val_A] = val_B
inc_stack.append(i)

# process elements that never had a next smaller or equal value
while inc_stack:
idx_val_A = inc_stack.pop()
ans[idx_val_A] = -1

return ans

nums = [14, 17, 13, 14, 14, 19, 12, 14, 18]
print(fn(nums)) # [13, 13, 12, 14, 12, 12, -1, -1, -1]
Intuition

The current value being processed, val_B, is always the next value in relation to whatever values are in the stack (since the stack is comprised of values encountered before the current value); hence, for another value, val_A, to have val_B as its next smaller or equal value, the value val_A will need to be popped from the stack, and it will need to be larger than or equal (>=) to the current value, val_B.

Maintaining a strictly increasing monotonic stack is perfectly suited for solving this problem. To see why, consider what would need to happen if we tried adding 8 to the following stack: [3, 4, 8, 9].

  • Is 9 greater than or equal to 8? Yes. Pop 9 from the stack, and note that 9's next smaller or equal value is 8. Stack's new state: [3, 4, 8].
  • Is 8 greater than or equal to 8? Yes. Pop 8 from the stack, and note that 8's next smaller or equal value is 8. Stack's new state: [3, 4].
  • Is 4 greater than or equal to 8? No. Push 8 to the stack. Stack's new state: [3, 4, 8]. Continue to next element.

This is how each "next smaller or equal value" is determined.

General template for "next value" problems

All of the approaches above are very similar except largely the kind of monotonic stack used to find elements satisfying the specified criteria. The following is a generalized template that can be slightly tweaked to get the desired result (only the comparison operator ? in the while loop's conditional, nums[stack[-1]] ? val_B, has to be changed):

def fn(nums):
n = len(nums)
ans = [None] * n
stack = [] # monotonic stack
for i in range(n):
val_B = nums[i]
# the comparison operator (?) dictates what A's next value B represents
# (<) next larger value (weakly decreasing stack)
# (<=) next larger or equal value (strictly decreasing stack)
# (>) next smaller value (weakly increasing stack)
# (>=) next smaller or equal value (strictly increasing stack)
while stack and nums[stack[-1]] ? val_B:
idx_val_A = stack.pop()
ans[idx_val_A] = val_B
stack.append(i)

# process elements that never had a "next" value that satisfied the criteria
while stack:
idx_val_A = stack.pop()
ans[idx_val_A] = -1

return ans
What happens if we use == or != for value comparison when managing our collection?
caution

It's probably best to skip this for now unless you're fully comfortable with everything that has been previously discussed in this post. The brief considerations we're about to make are likely to cause confusion and will add little to no (maybe negative?) benefit. If you're not yet deterred, then it might possibly be useful to concretely see why using these comparisons adds little value to our analyses.

Using the equality comparison: ==

TLDR: The answer array is only ever updated (i.e., ans[i] = curr_num) when equivalent values are adjacent: if nums[i] == nums[i+1], then the assignment ans[i] = nums[i+1] will be made. But this is the only scenario where updates are made (probably not a desirable nor useful effect).


It's tempting to think we're asking, "What is the next value equal to the current value?" This is somewhat of a ridiculous question since any value will clearly be its own next equal value if this value is ever repeated (the question of whether or not the value is ever repeated is the real question here). If our code actually attempted to answer this question by only changing the comparison operator to ==, then we would expect the following input-output result:

# Input
[14, 17, 13, 14, 14, 19, 12, 14, 18]

# Output
[14, -1, -1, 14, 14, -1, -1, -1, -1]

Let's run the code and see what we get (we'll add a helpful print statement too for clarification):

Input-Output
def fn(nums):
collection = []
ans = [-1] * len(nums)

for i in range(len(nums)):
curr_num = nums[i]
while collection and nums[collection[-1]] == curr_num:
prev_index = collection.pop()
ans[prev_index] = curr_num
collection.append(i)
print(
f'collection: {collection}; '
f'number correspondence: {[nums[idx] for idx in collection]}'
)

return ans

nums = [14, 17, 13, 14, 14, 19, 12, 14, 18] # Input
fn(nums) # Output: [-1, -1, -1, 14, -1, -1, -1, -1, -1]
Printed information
Index: 0;  Value: 14  Index collection: [0]                       Collection values: [14];                              Answer array: [-1, -1, -1, -1, -1, -1, -1, -1, -1]
Index: 1; Value: 17 Index collection: [0, 1] Collection values: [14, 17]; Answer array: [-1, -1, -1, -1, -1, -1, -1, -1, -1]
Index: 2; Value: 13 Index collection: [0, 1, 2] Collection values: [14, 17, 13]; Answer array: [-1, -1, -1, -1, -1, -1, -1, -1, -1]
Index: 3; Value: 14 Index collection: [0, 1, 2, 3] Collection values: [14, 17, 13, 14]; Answer array: [-1, -1, -1, -1, -1, -1, -1, -1, -1]
Index: 4; Value: 14 Index collection: [0, 1, 2, 4] Collection values: [14, 17, 13, 14]; Answer array: [-1, -1, -1, 14, -1, -1, -1, -1, -1]
Index: 5; Value: 19 Index collection: [0, 1, 2, 4, 5] Collection values: [14, 17, 13, 14, 19]; Answer array: [-1, -1, -1, 14, -1, -1, -1, -1, -1]
Index: 6; Value: 12 Index collection: [0, 1, 2, 4, 5, 6] Collection values: [14, 17, 13, 14, 19, 12]; Answer array: [-1, -1, -1, 14, -1, -1, -1, -1, -1]
Index: 7; Value: 14 Index collection: [0, 1, 2, 4, 5, 6, 7] Collection values: [14, 17, 13, 14, 19, 12, 14]; Answer array: [-1, -1, -1, 14, -1, -1, -1, -1, -1]
Index: 8; Value: 18 Index collection: [0, 1, 2, 4, 5, 6, 7, 8] Collection values: [14, 17, 13, 14, 19, 12, 14, 18]; Answer array: [-1, -1, -1, 14, -1, -1, -1, -1, -1]

What's going on here? Why is the answer array only updated once (after the value at index 4 is processed)? The answer isn't obvious at first and even gave ChatGPT 4 quite a few issues (you can ignore the first two messages in the ChatGPT thread). We can answer our own question by looking at the code more closely and determining what changing the comparison to == actually does. Here's the core part of the function:

for i in range(len(nums)):
curr_num = nums[i]
while collection and nums[collection[-1]] == curr_num:
prev_index = collection.pop()
ans[prev_index] = curr_num
collection.append(i)

When exactly are values added to collection? Once all previous values that equal the current value have been removed. For example, if the current number is x and the collection before processing this number somehow corresponded to the numbers [a, b, d, c, g, f, x, x, x], then the collection's number correspondence' after processing the current number would be [a, b, d, c, g, f, x], where the three equivalent x values previously in the collection were removed (and their corresponding spots in the answer array updated). This explains the crucial logic in the function above, but we should note that the collection itself will never have adjacent indexes that represent equivalent values due to how the collection is being maintained; that is, to use the example above, we would never actually reach the state of [a, b, d, c, g, f, x, x, x]. We would first reach [a, b, d, c, g, f, x] and the collection would stay this way until we encountered a new value not equal to x.

This may be easier to understand if we introduce an actual number array that models the situation above (the number above each value corresponds to that value's index):

        0  1  2  3  4  5  6   7   8   9
nums = [1, 2, 4, 3, 7, 6, 24, 24, 24, 24]

Eventually our collection of index values reaches the state [0, 1, 2, 3, 4, 5, 6], where nums[6] == 24, and we know the next three values are all 24; that is, nums[6] == nums[7] == nums[8] == nums[9]. How is collection maintained and how is our answer array updated?

  • Collection: [0, 1, 2, 3, 4, 5, 6]. Current value (index 7): 24. We have nums[6] == nums[7].
    • Pop 6
    • Update answer array: ans[6] = 24
    • Append 7 to the collection
  • Collection: [0, 1, 2, 3, 4, 5, 7]. Current value (index 8): 24. We have nums[7] == nums[8].
    • Pop 7
    • Update answer array: ans[7] = 24
    • Append 8 to the collection
  • Collection: [0, 1, 2, 3, 4, 5, 8]. Current value (index 9): 24. We have nums[8] == nums[9].
    • Pop 8
    • Update answer array: ans[8] = 24
    • Append 9 to the collection

This is where we'd stop because we just processed the last value in nums at index 9. Since the answer array is not updated at all until index 6, and is then updated in the manner above, our final answer array would be [-1, -1, -1, -1, -1, 24, 24, 24, -1]. If we execute the fn function above with nums = [1, 2, 4, 3, 7, 6, 24, 24, 24, 24] as the input, then this is exactly what we will get as the output.

For the sake of completeness, here's a way to answer the question we originally thought we might be asking (i.e., what is the next equal value or -1 if no such value exists):

def fn(nums):
collection = set()
ans = [None] * len(nums)
for i in range(len(nums) - 1, -1, -1):
curr_num = nums[i]
if curr_num in collection:
ans[i] = curr_num
else:
ans[i] = -1
collection.add(curr_num)
return ans

nums = [14, 17, 13, 14, 14, 19, 12, 14, 18]
fn(nums) # [14, -1, -1, 14, 14, -1, -1, -1, -1]
Using the inequality comparison: !=

TLDR: The answer array is updated whenever unequal values are adjacent. If two or more adjacent values are equal, then the indexes that represent these values are all added to the index collection, and the answer array is not updated until an unequal value is found, at which point all previous equal adjacent values are assigned this current unequal value in the answer array.

Due to the last in first out nature of how values are being maintained in the index collection, the effect of changing the comparison operator to != is that the answer array effectively tells us what each value's next unequal value will be (or -1 if no such value exists). This isn't entirely worthless, but it is also probably not the most desired effect nor all that useful a result.


If we change the comparison operator to !=, then it seems like we may be asking the following question: "What is the next value not equal to the current value?" And we'd be right (unlike before with ==) even though the result is unlikely to be all that useful! If we change the comparison operator to !=, then we would expect our code to produce the following input-output result:

# Input
[14, 17, 13, 14, 14, 19, 12, 14, 18]

# Output
[17, 13, 14, 19, 19, 12, 14, 18, -1]

Let's run the code and see what we get (we'll again add a helpful print statement for clarification):

Input-Output
def fn(nums):
collection = []
ans = [-1] * len(nums)

for i in range(len(nums)):
curr_num = nums[i]
while collection and nums[collection[-1]] != curr_num:
prev_index = collection.pop()
ans[prev_index] = curr_num
collection.append(i)
print(
f'Index: {i}; ',
f'Value: {nums[i]}',
f'Index collection: {collection}',
f'Collection values: {[nums[idx] for idx in collection]}; ',
f'Answer array: {ans}'
)

return ans

nums = [14, 17, 13, 14, 14, 19, 12, 14, 18] # Input
fn(nums) # Output: [17, 13, 14, 19, 19, 12, 14, 18, -1]
Printed information
Index: 0;  Value: 14  Index collection: [0]     Collection values: [14];      Answer array: [-1, -1, -1, -1, -1, -1, -1, -1, -1]
Index: 1; Value: 17 Index collection: [1] Collection values: [17]; Answer array: [17, -1, -1, -1, -1, -1, -1, -1, -1]
Index: 2; Value: 13 Index collection: [2] Collection values: [13]; Answer array: [17, 13, -1, -1, -1, -1, -1, -1, -1]
Index: 3; Value: 14 Index collection: [3] Collection values: [14]; Answer array: [17, 13, 14, -1, -1, -1, -1, -1, -1]
Index: 4; Value: 14 Index collection: [3, 4] Collection values: [14, 14]; Answer array: [17, 13, 14, -1, -1, -1, -1, -1, -1]
Index: 5; Value: 19 Index collection: [5] Collection values: [19]; Answer array: [17, 13, 14, 19, 19, -1, -1, -1, -1]
Index: 6; Value: 12 Index collection: [6] Collection values: [12]; Answer array: [17, 13, 14, 19, 19, 12, -1, -1, -1]
Index: 7; Value: 14 Index collection: [7] Collection values: [14]; Answer array: [17, 13, 14, 19, 19, 12, 14, -1, -1]
Index: 8; Value: 18 Index collection: [8] Collection values: [18]; Answer array: [17, 13, 14, 19, 19, 12, 14, 18, -1]

This is nice because we're actually getting the expected behavior here! But why though? Let's take a closer look at the core part of the function where the comparison operator for maintaining our index collection is now !=:

for i in range(len(nums)):
curr_num = nums[i]
while collection and nums[collection[-1]] != curr_num:
prev_index = collection.pop()
ans[prev_index] = curr_num
collection.append(i)

This effectively means the answer array gets updated every time we encounter a value not equal to the value represented at the top of the collection. But if the values are equal, as is the case above when the values of 14 are adjacent, then the answer array is not updated, and we wait until the next unequal value is encountered, at which point all previous adjacent values that are equivalent will be popped from the collection and assigned the current uneqal value in the answer array. This is actually the desired effect (even though it doesn't seem particularly useful).

Tabular summary

The tabular summary below compactly describes the examples used to illustrate the approaches in each solution above.

NEXT criteriacomparisonmonotonic stack typeexample stackcurrent valuedescription
next larger value<weakly decreasing[8, 6, 5, 4, 4]5The current value of 5 serves as the next larger value for both 4's on the stack, which are popped in order to make room for the 5, resulting in the following new weakly decreasing monotonic stack: [8, 6, 5, 5].
next larger or equal value<=strictly decreasing[8, 6, 5, 4]5The current value of 5 serves as the next larger or equal value for the 4 and 5 currently on the stack, which are popped in order to make room for the 5, resulting in the following new strictly decreasing monotonic stack: [8, 6, 5].
next smaller value>weakly increasing[3, 4, 8, 9, 9]8The current value of 8 serves as the next smaller value for both 9's on the stack, which are popped in order to make room for the 8, resulting in the following new weakly increasing monotonic stack: [3, 4, 8, 8].
next smaller or equal value>=strictly increasing[3, 4, 8, 9]8The current value of 8 serves as the next smaller or equal value for the 9 and 8 currently on the stack, which are popped in order to make room for the 8, resulting in the following new strictly increasing monotonic stack: [3, 4, 8].

Common problem (with template): Find a value's "previous" larger/smaller (or equal) value

Monotonic stacks below contain index values

Monotonic stacks will very often not contain the input array's values themselves but the indexes which point to these values. This makes it possible for us to not only get access to the array values themselves but also to positional information about where the array values reside. This can be confusing at first though if you are only used to seeing monotonic stacks that directly use array values.

Consult the template and/or tabular summary as reference points

The previous value template and/or previous value "tabular summary", which appear after the provided solutions/approaches to the questions posed in the bulleted list below, can be quite helpful to use as reference points while working through the various approaches.

Another common use case for a monotonic stack (although not as common as the ones immediately above) is to determine each value's "previous" larger/smaller (or equal) value (i.e., the value that comes to the left of a given value that meets the desired criteria):

  • Previous larger value: Given value A, what is the previous value B such that A < B?
  • Previous larger or equal value: Given value A, what is the previous value B such that A <= B?
  • Previous smaller value: Given value A, what is the previous value B such that A > B?
  • Previous smaller or equal value: Given value A, what is the previous value B such that A >= B?

Note that the value A referred to above will always be in reference to the current value being processed (i.e., the element we're about to add to the stack). Its previous value, which satisfies some criteria, must be in the monotonic stack (since the monotonic stack is always comprised of previous elements we've encountered, oldest to newest, left to right). The idea is to keep popping elements from the monotonic stack that do not meet our desired criteria until either the stack is empty (no previous value meeting the criteria was found) or the last element in the stack does satisfy the criteria, in which case it will be value A's previous value that meets the criteria. To illustrate this more clearly, each problem variation in the bulleted list above is solved below where the roles of "values A and B" have been explicitly designated in each solution (i.e., value B always refers to value A's previous value that meets the specified criteria).

The following array of numbers will be used as input in each solution approach for the sake of clarity and consistency:

nums = [14, 17, 13, 14, 14, 19, 12, 14, 18]

Values that ultimately end up having no previous value that satisfies the specified criteria will report a "previous value" of -1 in the answer array to communicate this. The answer array, ans, is always initialized to the length of the input array and filled with None values. This is done to concretely show how every element is processed.

Previous larger value

def fn(nums):
n = len(nums)
ans = [None] * n
dec_stack = [] # monotonic stack (strictly decreasing)
for i in range(n):
val_A = nums[i]
while dec_stack and nums[dec_stack[-1]] <= val_A:
dec_stack.pop()

if dec_stack:
idx_val_B = dec_stack[-1]
val_B = nums[idx_val_B]
ans[i] = val_B
else:
ans[i] = -1

dec_stack.append(i)

return ans

nums = [14, 17, 13, 14, 14, 19, 12, 14, 18]
print(fn(nums)) # [-1, -1, 17, 17, 17, -1, 19, 19, 19]
Intuition

The current value being processed, val_A, is always looking for its criteria-satisfying previous value from the stack (since the stack is comprised of values encountered previously to the current value). All previously encountered values that do not satisfy the specified criteria should be removed from the stack. There are two possibilities once such removals are made: either the stack is empty, in which case val_A has no criteria-satisfying previous value, or the stack is not empty, in which case the element on the top of the stack, val_B, is val_A's previous value that satisfies the specified criteria.

For this problem, if the current value, val_A, has a previous larger value, val_B, then val_B must reside in the stack. To access this value, we remove all elements from the stack that are smaller than or equal (<=) to val_A, ensuring the next value on top of the stack (if it exists) is larger than val_A, which is what we want. If the stack is empty after removing all values smaller than or equal to val_A, then there cannot be a previous value, val_B, such that val_B > val_A. If, however, the stack is not empty after removing all values smaller than or equal to val_A, then whatever element resides at the top of the stack is val_B, where val_B > val_A.

Maintaining a strictly decreasing monotonic stack is perfectly suited for solving this problem. To see why, consider what would need to happen if we tried adding 5 to the following stack: [8, 6, 5, 4].

  • Is 4 less than or equal to 5? Yes. Pop 4 from the stack. Stack's new state: [8, 6, 5].
  • Is 5 less than or equal to 5? Yes. Pop 5 from the stack. Stack's new state: [8, 6].
  • Is 6 less than or equal to 5? No. Since the stack is not empty, 6 must be 5's previous larger value. Push 5 to the stack. Stack's new state: [8, 6, 5]. Continue to next element.

This is how each "previous larger value" is determined.

Previous larger or equal value

def fn(nums):
n = len(nums)
ans = [None] * n
dec_stack = [] # monotonic stack (weakly decreasing)
for i in range(n):
val_A = nums[i]
while dec_stack and nums[dec_stack[-1]] < val_A:
dec_stack.pop()

if dec_stack:
idx_val_B = dec_stack[-1]
val_B = nums[idx_val_B]
ans[i] = val_B
else:
ans[i] = -1

dec_stack.append(i)

return ans

nums = [14, 17, 13, 14, 14, 19, 12, 14, 18]
print(fn(nums)) # [-1, -1, 17, 17, 14, -1, 19, 19, 19]
Intuition

The current value being processed, val_A, is always looking for its criteria-satisfying previous value from the stack (since the stack is comprised of values encountered previously to the current value). All previously encountered values that do not satisfy the specified criteria should be removed from the stack. There are two possibilities once such removals are made: either the stack is empty, in which case val_A has no criteria-satisfying previous value, or the stack is not empty, in which case the element on the top of the stack, val_B, is val_A's previous value that satisfies the specified criteria.

For this problem, if the current value, val_A, has a previous larger or equal value, val_B, then val_B must reside in the stack. To access this value, we remove all elements from the stack that are smaller (<) than val_A, ensuring the next value on top of the stack (if it exists) is larger than or equal to val_A, which is what we want. If the stack is empty after removing all values smaller than val_A, then there cannot be a previous value, val_B, such that val_B >= val_A. If, however, the stack is not empty after removing all values smaller than or equal to val_A, then whatever element resides at the top of the stack is val_B, where val_B >= val_A.

Maintaining a weakly decreasing monotonic stack is perfectly suited for solving this problem. To see why, consider what would need to happen if we tried adding 5 to the following stack: [8, 6, 5, 4, 4].

  • Is 4 less than 5? Yes. Pop 4 from the stack. Stack's new state: [8, 6, 5, 4].
  • Is 4 less than 5? Yes. Pop 4 from the stack. Stack's new state: [8, 6, 5].
  • Is 5 less than 5? No. Since the stack is not empty, 5 must be 5's previous larger or equal value. Push 5 to the stack. Stack's new state: [8, 6, 5, 5]. Continue to next element.

This is how each "previous larger or equal value" is determined.

Previous smaller value

def fn(nums):
n = len(nums)
ans = [None] * n
inc_stack = [] # monotonic stack (strictly increasing)
for i in range(n):
val_A = nums[i]
while inc_stack and nums[inc_stack[-1]] >= val_A:
inc_stack.pop()

if inc_stack:
idx_val_B = inc_stack[-1]
val_B = nums[idx_val_B]
ans[i] = val_B
else:
ans[i] = -1

inc_stack.append(i)

return ans

nums = [14, 17, 13, 14, 14, 19, 12, 14, 18]
print(fn(nums)) # [-1, 14, -1, 13, 13, 14, -1, 12, 14]
Intuition

The current value being processed, val_A, is always looking for its criteria-satisfying previous value from the stack (since the stack is comprised of values encountered previously to the current value). All previously encountered values that do not satisfy the specified criteria should be removed from the stack. There are two possibilities once such removals are made: either the stack is empty, in which case val_A has no criteria-satisfying previous value, or the stack is not empty, in which case the element on the top of the stack, val_B, is val_A's previous value that satisfies the specified criteria.

For this problem, if the current value, val_A, has a previous smaller value, val_B, then val_B must reside in the stack. To access this value, we remove all elements from the stack that are larger than or equal (>=) to val_A, ensuring the next value on top of the stack (if it exists) is smaller than val_A, which is what we want. If the stack is empty after removing all values larger than or equal to val_A, then there cannot be a previous value, val_B, such that val_B < val_A. If, however, the stack is not empty after removing all values larger than or equal to val_A, then whatever element resides at the top of the stack is val_B, where val_B < val_A.

Maintaining a strictly increasing monotonic stack is perfectly suited for solving this problem. To see why, consider what would need to happen if we tried adding 5 to the following stack: [4, 5, 6, 8].

  • Is 8 greater than or equal to 5? Yes. Pop 8 from the stack. Stack's new state: [4, 5, 6].
  • Is 6 greater than or equal to 5? Yes. Pop 6 from the stack. Stack's new state: [4, 5].
  • Is 5 greater than or equal to 5? Yes. Pop 5 from the stack. Stack's new state: [4].
  • Is 4 greater than or equal to 5? No. Since the stack is not empty, 4 must be 5's previous smaller value. Push 5 to the stack. Stack's new state: [4, 5]. Continue to next element.

This is how each "previous smaller value" is determined.

Previous smaller or equal value

def fn(nums):
n = len(nums)
ans = [None] * n
inc_stack = [] # monotonic stack (weakly increasing)
for i in range(n):
val_A = nums[i]
while inc_stack and nums[inc_stack[-1]] > val_A:
inc_stack.pop()

if inc_stack:
idx_val_B = inc_stack[-1]
val_B = nums[idx_val_B]
ans[i] = val_B
else:
ans[i] = -1

inc_stack.append(i)

return ans

nums = [14, 17, 13, 14, 14, 19, 12, 14, 18]
print(fn(nums)) # [-1, 14, -1, 13, 14, 14, -1, 12, 14]
Intuition

The current value being processed, val_A, is always looking for its criteria-satisfying previous value from the stack (since the stack is comprised of values encountered previously to the current value). All previously encountered values that do not satisfy the specified criteria should be removed from the stack. There are two possibilities once such removals are made: either the stack is empty, in which case val_A has no criteria-satisfying previous value, or the stack is not empty, in which case the element on the top of the stack, val_B, is val_A's previous value that satisfies the specified criteria.

For this problem, if the current value, val_A, has a previous smaller or equal value, val_B, then val_B must reside in the stack. To access this value, we remove all elements from the stack that are larger (>) than val_A, ensuring the next value on top of the stack (if it exists) is smaller than or equal to val_A, which is what we want. If the stack is empty after removing all values larger than val_A, then there cannot be a previous value, val_B, such that val_B <= val_A. If, however, the stack is not empty after removing all values larger than val_A, then whatever element resides at the top of the stack is val_B, where val_B <= val_A.

Maintaining a weakly increasing monotonic stack is perfectly suited for solving this problem. To see why, consider what would need to happen if we tried adding 5 to the following stack: [4, 5, 8, 8].

  • Is 8 greater than 5? Yes. Pop 8 from the stack. Stack's new state: [4, 5, 8].
  • Is 8 greater than 5? Yes. Pop 8 from the stack. Stack's new state: [4, 5].
  • Is 5 greater than 5? No. Since the stack is not empty, 5 must be 5's previous smaller or equal value. Push 5 to the stack. Stack's new state: [4, 5, 5]. Continue to next element.

This is how each "previous smaller or equal value" is determined.

General template for "previous value" problems

def fn(nums):
n = len(nums)
ans = [None] * n
stack = [] # monotonic stack
for i in range(n):
val_A = nums[i]
# the comparison operator (?) dictates what A's previous value B represents
# (<=) previous larger (strictly decreasing)
# (<) previous larger or equal value (weakly decreasing)
# (>=) previous smaller value (strictly increasing)
# (>) previous smaller or equal value (weakly increasing)
while stack and nums[stack[-1]] ? val_A:
stack.pop()

if stack:
idx_val_B = stack[-1]
val_B = nums[idx_val_B]
ans[i] = val_B
else:
ans[i] = -1

stack.append(i)

return ans

Tabular summary

The tabular summary below compactly describes the examples used to illustrate the approaches in each solution above.

PREVIOUS criteriacomparisonmonotonic stack typeexample stackcurrent valuedescription
previous larger value<=strictly decreasing[8, 6, 5, 4]5The previously encountered values of 4 and 5 are popped off the stack, respectively. Since the stack is now [8, 6], this means the previous larger value for 5 is 6, the element now on top of the stack (if the stack were empty after the removals, then 5 would have no previous larger value). We now add 5 to the stack and continue processing elements: [8, 6, 5].
previous larger or equal value<weakly decreasing[8, 6, 5, 4, 4]5The previously encountered values of 4 and 4 are popped off the stack, respectively. Since the stack is now [8, 6, 5], this means the previous larger value for 5 is 5, the element now on top of the stack (if the stack were empty after the removals, then 5 would have no previous larger value). We now add 5 to the stack and continue processing elements: [8, 6, 5, 5].
previous smaller value>=strictly increasing[4, 5, 6, 8]5The previously encountered values of 8, 6, and 5 are popped off the stack, respectively. Since the stack is now [4], this means the previous smaller value for 5 is 4, the element now on top of the stack (if the stack were empty after the removals, then 5 would have no previous smaller value). We now add 4 to the stack and continue processing elements: [4, 5].
previous smaller or equal value>weakly increasing[4, 5, 8, 8]5The previously encountered values of 8 and 8 are popped off the stack, respectively. Since the stack is now [4, 5], this means the previous smaller value for 5 is 4, the element now on top of the stack (if the stack were empty after the removals, then 5 would have no previous smaller value). We now add 4 to the stack and continue processing elements: [4, 5].

Common problems combined: In one pass, find each value's "next" AND "previous" value based on monotonic invariant

The last bullet point in the important observations section (i.e., the bullet point right above the monotonic stack definition) illustrates how it's possible to make "next" and "previous" value determinations as we process each element before adding it to the monotonic stack. Let's examine how we might be able to do this efficiently by combining the two templates from the two sections above:

General template for "next value" problems
def fn(nums):
n = len(nums)
ans = [None] * n
stack = [] # monotonic stack
for i in range(n):
val_B = nums[i]
# the comparison operator (?) dictates what A's next value B represents
# (<) next larger value (weakly decreasing stack)
# (<=) next larger or equal value (strictly decreasing stack)
# (>) next smaller value (weakly increasing stack)
# (>=) next smaller or equal value (strictly increasing stack)
while stack and nums[stack[-1]] ? val_B:
idx_val_A = stack.pop()
ans[idx_val_A] = val_B

# why shouldn't we make a "previous value" determination here
# before adding the current element to the stack?

stack.append(i)

# process elements that never had a "next" value that satisfied the criteria
while stack:
idx_val_A = stack.pop()
ans[idx_val_A] = -1

return ans
General template for "previous value" problems
def fn(nums):
n = len(nums)
ans = [None] * n
stack = [] # monotonic stack
for i in range(n):
val_A = nums[i]
# the comparison operator (?) dictates what A's previous value B represents
# (<=) previous larger (strictly decreasing)
# (<) previous larger or equal value (weakly decreasing)
# (>=) previous smaller value (strictly increasing)
# (>) previous smaller or equal value (weakly increasing)
while stack and nums[stack[-1]] ? val_A:
stack.pop() # this template currently does not do anything with this value

# why shouldn't we make "next value" determinations here
# instead of doing nothing with the values popped from the stack?


if stack:
idx_val_B = stack[-1]
val_B = nums[idx_val_B]
ans[i] = val_B
else:
ans[i] = -1

stack.append(i)

return ans

Let's try to combine these templates by resolving the issues highlighted above. Our answer array will now be a list of lists structured in the following way: ans[i] == [prev, next], where prev and next indicate the "previous" and "next" values for each element at index i (i.e., the element nums[i]). Here's one way of doing this:

def fn(nums):
n = len(nums)
ans = [[None, None] for _ in range(n)]
stack = []

# the comparison operator (?) dictates what each element's PREVIOUS and NEXT values will be
# (<=) PREVIOUS larger value and NEXT larger or equal value (strictly decreasing stack)
# (<) PREVIOUS larger or equal value and NEXT larger value (weakly decreasing stack)
# (>=) PREVIOUS smaller value and NEXT smaller or equal value (strictly increasing stack)
# (>) PREVIOUS smaller or equal value and NEXT smaller value (weakly increasing stack)
for i in range(n):
while stack and nums[stack[-1]] ? nums[i]:
idx = stack.pop() # NEXT values are now processed for each element popped from the stack
ans[idx][1] = i

# PREVIOUS value for current element is now processed (before adding it to the stack)
if stack:
ans[i][0] = stack[-1]
else:
ans[i][0] = -1

stack.append(i)

# process remaining values that had no "next" value
while stack:
idx = stack.pop()
ans[idx][1] = -1

return ans
Initialization of answer array

Answer arrays are often initialized as ans = [-1] * n, ans = [None] * n, etc., but it would be a mistake if we tried initializing ans in the combined template above as ans = [[None, None]] * n. Why? This expression essentially creates a list containing n references to the same list: [None, None]; hence, if one of these lists is modified, then all of them get modified (because they all refer to the same list in memory). That's definitely not the intention! This is because entities such as -1, None, etc., are values and not references whereas lists are references. The simple fix for this issue is to simply create n distinct lists in ans, where each list starts as [None, None].

If we allow ourselves the freedom to tidy things up a bit, then we can express the code above in a much more concise manner (by condensing logic as well as removing code comments):

def fn(nums):
n = len(nums)
ans = [[-1, -1] for _ in range(n)]
stack = []
for i in range(n):
while stack and nums[stack[-1]] ? nums[i]:
idx = stack.pop()
ans[idx][1] = i
ans[i][0] = -1 if not stack else stack[-1]
stack.append(i)
return ans

What changes were made above to condense things so much? See if you can determine that for yourself before looking at the final template below which contains several code comments:

Combined templates for finding previous and next values in a single pass
def fn(nums):
n = len(nums)
ans = [[-1, -1] for _ in range(n)] # default values for missing PREVIOUS and NEXT values, respectively
stack = [] # monotonic stack

# the comparison operator (?) dictates what each element's PREVIOUS and NEXT values will be
# (<=) PREVIOUS larger value and NEXT larger or equal value (strictly decreasing stack)
# (<) PREVIOUS larger or equal value and NEXT larger value (weakly decreasing stack)
# (>=) PREVIOUS smaller value and NEXT smaller or equal value (strictly increasing stack)
# (>) PREVIOUS smaller or equal value and NEXT smaller value (weakly increasing stack)
for i in range(n):
while stack and nums[stack[-1]] ? nums[i]:
# NEXT values processed
idx = stack.pop()
ans[idx][1] = i # use nums[i] instead of i to directly record array values instead of indexes
# PREVIOUS values processed
ans[i][0] = -1 if not stack else stack[-1] # use nums[stack[-1]] instead of stack[-1]
# to directly record array values instead of indexes
stack.append(i)

return ans

The template above is remarkably powerful given what it accomplishes in a single pass. If we execute fn on the sample input array nums = [3, 4, 4, 5, 4, 1], then we get the following outputs for each comparison operator used to maintain the stack invariant:

(<=) PREVIOUS larger, NEXT larger or equal
#  0  1  2  3  4  5  (index values)
# [3, 4, 4, 5, 4, 1] (input array)
# output:
[
[-1, 1], # previous larger value for nums[0] == 3 does not exist (-1)
# next larger or equal value for nums[0] == 3 is nums[1] == 4

[-1, 2], # previous larger value for nums[1] == 4 does not exist (-1)
# next larger or equal value for nums[1] == 4 is nums[2] == 4

[-1, 3], # previous larger value for nums[2] == 4 does not exist (-1)
# next larger or equal value for nums[2] == 4 is nums[3] == 5

[-1, -1], # previous larger value for nums[3] == 5 does not exist (-1)
# next larger or equal value for nums[3] == 5 does not exist (-1)

[ 3, -1], # previous larger value for nums[4] == 4 is nums[3] == 5
# next larger or equal value for nums[4] == 4 does not exist (-1)

[ 4, -1], # previous larger value for nums[5] == 1 is nums[4] == 5
# next larger or equal value for nums[5] == 1 does not exist (-1)
]
(<) PREVIOUS larger or equal, NEXT larger
#  0  1  2  3  4  5  (index values)
# [3, 4, 4, 5, 4, 1] (input array)
# output:
[
[-1, 1], # previous larger or equal value for nums[0] == 3 does not exist (-1)
# next larger value for nums[0] == 3 is nums[1] == 4

[-1, 3], # previous larger or equal value for nums[1] == 4 does not exist (-1)
# next larger value for nums[1] == 4 is nums[3] == 5

[ 1, 3], # previous larger or equal value for nums[2] == 4 does not exist (-1)
# next larger value for nums[2] == 4 is nums[3] == 5

[-1, -1], # previous larger or equal value for nums[3] == 5 does not exist (-1)
# next larger value for nums[3] == 5 does not exist (-1)

[ 3, -1], # previous larger or equal value for nums[4] == 4 is nums[3] == 5
# next larger value for nums[4] == 4 does not exist (-1)

[ 4, -1], # previous larger or equal value for nums[5] == 1 is nums[4] == 5
# next larger value for nums[5] == 1 does not exist (-1)
]
(>=) PREVIOUS smaller, NEXT smaller or equal
#  0  1  2  3  4  5  (index values)
# [3, 4, 4, 5, 4, 1] (input array)
# output:
[
[-1, 5], # previous smaller value for nums[0] == 3 does not exist (-1)
# next smaller or equal value for nums[0] == 3 is nums[5] == 1

[ 0, 2], # previous smaller value for nums[1] == 4 is nums[0] == 3
# next smaller or equal value for nums[1] == 4 is nums[2] == 4

[ 0, 4], # previous smaller value for nums[2] == 4 is nums[0] == 3
# next smaller or equal value for nums[2] == 4 is nums[4] == 4

[ 2, 4], # previous smaller value for nums[3] == 5 is nums[2] == 4
# next smaller or equal value for nums[3] == 5 is nums[4] == 4

[ 0, 5], # previous smaller value for nums[4] == 4 is nums[0] == 3
# next smaller or equal value for nums[4] == 4 is nums[5] == 1

[-1, -1], # previous smaller value for nums[5] == 1 does not exist (-1)
# next smaller or equal value for nums[5] == 1 does not exist (-1)
]
(>) PREVIOUS smaller or equal, NEXT smaller
#  0  1  2  3  4  5  (index values)
# [3, 4, 4, 5, 4, 1] (input array)
# output:
[
[-1, 5], # previous smaller or equal value for nums[0] == 3 does not exist (-1)
# next smaller value for nums[0] == 3 is nums[5] == 1

[ 0, 5], # previous smaller or equal value for nums[1] == 4 is nums[0] == 3
# next smaller value for nums[1] == 4 is nums[5] == 1

[ 1, 5], # previous smaller or equal value for nums[2] == 4 is nums[1] == 4
# next smaller value for nums[2] == 4 is nums[5] == 1

[ 2, 4], # previous smaller or equal value for nums[3] == 5 is nums[2] == 4
# next smaller value for nums[3] == 5 is nums[4] == 4

[ 2, 5], # previous smaller or equal value for nums[4] == 4 is nums[2] == 4
# next smaller value for nums[4] == 4 is nums[5] == 1

[-1, -1], # previous smaller or equal value for nums[5] == 1 does not exist (-1)
# next smaller value for nums[5] == 1 does not exist (-1)
]

Templates for generalized monotonic stacks and deques

note

The content in this section is largely meant for standalone reference (i.e., it contains repeated information if you've read all of the previous content in this post). You can safely skip ahead to the LeetCode practice problems and/or the solved practice problems if you've read everything above in this post.

The templates below are constructed in a way such that the index values are being added to the stack or (double-ended) queue as opposed to the values themselves. This is because index values are often needed since they supply additional information and make it possible to distinguish between values that might otherwise be considered identical. For example, if nums = [1, 1], then nums[0] == nums[1] but 0 != 1; that is, the values of 1 are identicial but their indexed positions are not.

The foundation of all possible monotonic stack and queue templates is the same and hinges on two important pieces of information:

  1. Will elements possibly need to be removed from the left of the index collection at some point? If so, use a deque (otherwise use a simple stack). An element(s) is generally removed from the left of the deque after the deque's increasing/decreasing invariant has been maintained and the current element has been added to the right of the deque — usually some condition is violated that stipulates deque elements should be removed from the left (e.g., an invalid index for a sliding window is a common example).

    Maintaining the increasing/decreasing invariant for the collection (stack or deque) always uses stack-like operations: we remove from the right or top (i.e., "pop") every single value that would result in the invariant being violated once the current element is added to the right or top (i.e., "push"). In this sense, a monotonic "queue" is really a misnomer since the addition and removal of elements to maintain the invariant is always performed in LIFO fashion (last in first out); that is, the "push" and "pop" operations needed to maintain the deque invariant are fundamentally stack-like in nature. It's only if we need to remove elements from the left that the idea of a queue enters the picture, where a FIFO operation is needed (i.e., first in first out). Hence, we only ever really consider monotonic stacks or deques (double-ended queues).

  2. How do the values referred to in your index collection need to progress from left to right? Should the values be strictly increasing or strictly decreasing? Should duplicate values be allowed (i.e., weakly increasing or weakly decreasing)? The value comparison you use in the condition of the while loop determines what kind of invariant you will maintain for your index collection.

    The core part of maintaining the invariant for any index collection is the following:

    # ...
    for i in range(len(nums)):
    curr_num = nums[i]
    while index_collection and nums[index_collection[-1]] ? curr_num:
    index_collection.pop()
    index_collection.append(i)
    # ...

    Above, ? refers to the value comparison used to maintain the index collection's invariant. Solutions involving monotonic stacks generally involve finding each element's "next" or "previous" value in some comparative way (i.e., greater/smaler or equal to):

    Template for finding A's next value B
    def fn(nums):
    n = len(nums)
    ans = [None] * n
    stack = [] # monotonic stack
    for i in range(n):
    val_B = nums[i]
    # the comparison operator (?) dictates what A's next value B represents
    # (<) next larger value (weakly decreasing stack)
    # (<=) next larger or equal value (strictly decreasing stack)
    # (>) next smaller value (weakly increasing stack)
    # (>=) next smaller or equal value (strictly increasing stack)
    while stack and nums[stack[-1]] ? val_B:
    idx_val_A = stack.pop()
    ans[idx_val_A] = val_B
    stack.append(i)

    # process elements that never had a "next" value that satisfied the criteria
    while stack:
    idx_val_A = stack.pop()
    ans[idx_val_A] = -1

    return ans
    Template for finding A's previous value B
    def fn(nums):
    n = len(nums)
    ans = [None] * n
    stack = [] # monotonic stack
    for i in range(n):
    val_A = nums[i]
    # the comparison operator (?) dictates what A's previous value B represents
    # (<=) previous larger (strictly decreasing)
    # (<) previous larger or equal value (weakly decreasing)
    # (>=) previous smaller value (strictly increasing)
    # (>) previous smaller or equal value (weakly increasing)
    while stack and nums[stack[-1]] ? val_A:
    stack.pop()

    if stack:
    idx_val_B = stack[-1]
    val_B = nums[idx_val_B]
    ans[i] = val_B
    else:
    ans[i] = -1

    stack.append(i)

    return ans
    Combined templates for previous and next values
    def fn(nums):
    n = len(nums)
    ans = [[-1, -1] for _ in range(n)] # default values for missing PREVIOUS and NEXT values, respectively
    stack = [] # monotonic stack

    # the comparison operator (?) dictates what each element's PREVIOUS and NEXT values will be
    # (<=) PREVIOUS larger value and NEXT larger or equal value (strictly decreasing stack)
    # (<) PREVIOUS larger or equal value and NEXT larger value (weakly decreasing stack)
    # (>=) PREVIOUS smaller value and NEXT smaller or equal value (strictly increasing stack)
    # (>) PREVIOUS smaller or equal value and NEXT smaller value (weakly increasing stack)
    for i in range(n):
    while stack and nums[stack[-1]] ? nums[i]:
    # NEXT values processed
    idx = stack.pop()
    ans[idx][1] = i # use nums[i] instead of i to directly record array values instead of indexes
    # PREVIOUS values processed
    ans[i][0] = -1 if not stack else stack[-1] # use nums[stack[-1]] instead of stack[-1]
    # to directly record array values instead of indexes
    stack.append(i)

    return ans

    Solutions involving monotonic deques are usually almost identical to their monotonic stack equivalents but with the inclusion of some CONDITION being met that necessitates the removal of collection elements from the left. For example, suppose we're trying to find each element's next greater value, but we now have some CONDITION that, when met, means we need to remove the leftmost element of our collection:

    Monotonic deque (weakly decreasing)
    from collections import deque
    def fn(nums):
    dec_queue = deque()
    ans = []

    for i in range(len(nums)):
    curr_num = nums[i]
    while dec_queue and nums[dec_queue[-1]] < curr_num:
    dec_queue.pop()
    dec_queue.append(i)

    if CONDITION:
    dec_queue.popleft()

    return ans
    Monotonic stack (weakly decreasing)

    def fn(nums):
    dec_stack = []
    ans = []

    for i in range(len(nums)):
    curr_num = nums[i]
    while dec_stack and nums[dec_stack[-1]] < curr_num:
    dec_stack.pop()
    dec_stack.append(i)




    return ans

Monotonic stack

"Next height" problems solved with code template

All of the problems below use heights = [14, 17, 13, 14, 14, 19, 12, 14, 18] as the input. Each problem requests a height value in relation to the current height value — if such a value is not found, then -1 should be reported.

Next height greater than current height
def next_greater_height(heights):
dec_stack = [] # monotonically decreasing stack (duplicates allowed)
ans = [-1] * len(heights)

for i in range(len(heights)):
curr_height = heights[i]
while dec_stack and heights[dec_stack[-1]] < curr_height:
prev_height_index = dec_stack.pop()
ans[prev_height_index] = curr_height
dec_stack.append(i)

return ans
# Input
[14, 17, 13, 14, 14, 19, 12, 14, 18]

# Output
[17, 19, 14, 19, 19, -1, 14, 18, -1]
Next height greater than or equal to current height
def next_greater_than_or_equal_to_height(heights):
dec_stack = [] # monotonically decreasing stack (duplicates not allowed)
ans = [-1] * len(heights)

for i in range(len(heights)):
curr_height = heights[i]
while dec_stack and heights[dec_stack[-1]] <= curr_height:
prev_height_index = dec_stack.pop()
ans[prev_height_index] = curr_height
dec_stack.append(i)

return ans
# Input
[14, 17, 13, 14, 14, 19, 12, 14, 18]

# Output
[17, 19, 14, 14, 19, -1, 14, 18, -1]
Next height smaller than current height
def next_smaller_height(heights):
inc_stack = [] # monotonically increasing stack (duplicates allowed)
ans = [-1] * len(heights)

for i in range(len(heights)):
curr_height = heights[i]
while inc_stack and heights[inc_stack[-1]] > curr_height:
prev_height_index = inc_stack.pop()
ans[prev_height_index] = curr_height
inc_stack.append(i)

return ans
# Input
[14, 17, 13, 14, 14, 19, 12, 14, 18]

# Output
[13, 13, 12, 12, 12, 12, -1, -1, -1]
Next height smaller than or equal to current height
def next_smaller_than_or_equal_to_height(heights):
inc_stack = [] # monotonically increasing stack (duplicates not allowed)
ans = [-1] * len(heights)

for i in range(len(heights)):
curr_height = heights[i]
while inc_stack and heights[inc_stack[-1]] >= curr_height:
prev_height_index = inc_stack.pop()
ans[prev_height_index] = curr_height
inc_stack.append(i)

return ans
# Input
[14, 17, 13, 14, 14, 19, 12, 14, 18]

# Output
[13, 13, 12, 14, 12, 12, -1, -1, -1]
Monotonic stack (template for finding A's next value B)
def fn(nums):
n = len(nums)
ans = [None] * n
stack = [] # monotonic stack
for i in range(n):
val_B = nums[i]
# the comparison operator (?) dictates what A's next value B represents
# (<) next larger value (weakly decreasing stack)
# (<=) next larger or equal value (strictly decreasing stack)
# (>) next smaller value (weakly increasing stack)
# (>=) next smaller or equal value (strictly increasing stack)
while stack and nums[stack[-1]] ? val_B:
idx_val_A = stack.pop()
ans[idx_val_A] = val_B
stack.append(i)

# process elements that never had a "next" value that satisfied the criteria
while stack:
idx_val_A = stack.pop()
ans[idx_val_A] = -1

return ans
Monotonic stack (template for finding A's previous value B)
def fn(nums):
n = len(nums)
ans = [None] * n
stack = [] # monotonic stack
for i in range(n):
val_A = nums[i]
# the comparison operator (?) dictates what A's previous value B represents
# (<=) previous larger (strictly decreasing)
# (<) previous larger or equal value (weakly decreasing)
# (>=) previous smaller value (strictly increasing)
# (>) previous smaller or equal value (weakly increasing)
while stack and nums[stack[-1]] ? val_A:
stack.pop()

if stack:
idx_val_B = stack[-1]
val_B = nums[idx_val_B]
ans[i] = val_B
else:
ans[i] = -1

stack.append(i)

return ans
Monotonic stack (combined templates for previous and next values)
def fn(nums):
n = len(nums)
ans = [[-1, -1] for _ in range(n)] # default values for missing PREVIOUS and NEXT values, respectively
stack = [] # monotonic stack

# the comparison operator (?) dictates what each element's PREVIOUS and NEXT values will be
# (<=) PREVIOUS larger value and NEXT larger or equal value (strictly decreasing stack)
# (<) PREVIOUS larger or equal value and NEXT larger value (weakly decreasing stack)
# (>=) PREVIOUS smaller value and NEXT smaller or equal value (strictly increasing stack)
# (>) PREVIOUS smaller or equal value and NEXT smaller value (weakly increasing stack)
for i in range(n):
while stack and nums[stack[-1]] ? nums[i]:
# NEXT values processed
idx = stack.pop()
ans[idx][1] = i # use nums[i] instead of i to directly record array values instead of indexes
# PREVIOUS values processed
ans[i][0] = -1 if not stack else stack[-1] # use nums[stack[-1]] instead of stack[-1]
# to directly record array values instead of indexes
stack.append(i)

return ans

Monotonic queue (deque)

Sliding window minimum problem solved with code template

Recall the problem statement:

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return an answer array that contains the minimum value for each sliding window of size k. For example, if the input array is nums = [11, 13, -11, -13, 15, 13, 16, 17] and k = 3, then the desired output or answer array would be [-11, -13, -13, -13, 13, 13].

The following illustration shows why the example above has the input and output it does:

Window position                         Min ------------------------               ----- [11  13  -11] -13  15  13  16  17       -11  11 [13  -11  -13] 15  13  16  17       -13  11  13 [-11  -13  15] 13  16  17       -13  11  13  -11 [-13  15  13] 16  17       -13  11  13  -11  -13 [15  13  16] 17        13  11  13  -11  -13  15 [13  16  17]       13

Now for the solution based on the template code:

from collections import deque

def sliding_window_min(nums, k):
queue = deque() # monotonic deque (weakly increasing)
ans = []

for i in range(len(nums)):
curr_num = nums[i]
while queue and nums[queue[-1]] > curr_num:
queue.pop()
queue.append(i)

# remove the leftmost deque element if it is the leftmost index of the previous window
# (i.e., it is not a valid index for the _current_ window)
if queue[0] == i - k:
queue.popleft()

# only start adding to the answer array
# once the window has grown to the required size
if i >= k - 1:
ans.append(nums[queue[0]])

return ans
from collections import deque

def fn(nums):
queue = deque() # monotonic deque
ans = []

for i in range(n):
val_B = nums[i]
# the comparison operator (?) dictates what A's next value B represents
# (<) next larger value (weakly decreasing queue)
# (<=) next larger or equal value (strictly decreasing queue)
# (>) next smaller value (weakly increasing queue)
# (>=) next smaller or equal value (strictly increasing queue)
while queue and nums[queue[-1]] ? val_B:
idx_val_A = queue.pop()
ans[idx_val_A] = val_B
queue.append(i)

if CONDITION:
queue.popleft()

# process elements that never had a "next" value that satisfied the criteria
while queue:
idx_val_A = queue.pop()
ans[idx_val_A] = -1

return ans

LeetCode practice problems

There are many ways to practice solving problems where monotonic stacks or (double-ended) queues play a pivotal role in crafting an optimal solution. LeetCode itself is a treasure trove for these kinds of problems.

Monotonic stacks

There are currently 58 problems on LeetCode tagged as being monotonic stack problems:

Monotonic queues

There are currently 15 problems on LeetCode tagged as being monotonic queue problems:

Solved practice problems

The problems below all appear on the LeetCode platform. The notation used in many of the provided solutions matches the notation used in the templates for "next" and "previous" values for the sake of clarity (this arguably makes it easier to see exactly how each template is being applied and/or modified).

Each solved practice problem consists of three elements:

  1. The problem statement (followed by a horizontal dividing line). If you want to see examples of desired outputs for different inputs, then right-click the problem title in each widget to visit the link to view the problem in its entirety on the LeetCode platform.
  2. An accepted solution (i.e., a solution which is accepted for the given problem on the LeetCode platform).
  3. Commentary on the provided solution that is accepted (minimal in some cases and quite extensive in others).

The final two solved practice problems, LC 907. Sum of Subarray Minimums and LC 2104. Sum of Subarray Ranges, are addressed more thoroughly in this post's "epilogue".

LC 739. Daily Temperatures

Given an array of integers temperatures that represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.


class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
ans = [None] * n
stack = []

for i in range(n):
val_A = temperatures[i]
# try to find the next larger temperature, val_B,
# for the current temperature, val_A
while stack and temperatures[stack[-1]] < val_A:
idx_val_B = stack.pop()
ans[idx_val_B] = i - idx_val_B
stack.append(i)

# remaining temperatures, val_A, have no next larger temperature, val_B
while stack:
idx_val_A = stack.pop()
ans[idx_val_A] = 0

return ans

The approach above is almost a direct application of the template for next value problems, where we're trying to find the next larger value for each value we encounter. We use the difference in indexes to determine how many days there are to wait.

LC 239. Sliding Window Maximum

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.


class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
dec_queue = deque() # monotonic deque (weakly decreasing)
ans = []
for i in range(n):
curr_num = nums[i]
# maintain the weakly decreasing deque
while dec_queue and nums[dec_queue[-1]] < curr_num:
dec_queue.pop()

# check to see if leftmost value of the deque
# is now actually an invalid index
if dec_queue and dec_queue[0] == i - k:
dec_queue.popleft()

dec_queue.append(i)

# only add window maximums to the answer array
# once the required length has been reached
if i >= k - 1:
ans.append(nums[dec_queue[0]])

return ans

We're not trying to find a "next" or "previous" anything. We're trying to maintain a sliding window maximum. A monotonic deque that is weakly decreasing is the tool of choice here (weakly decreasing instead of strictly since the same window can have duplicated maxima) since access to the leftmost element will always be the maximum. Additionally, if sliding the window results in invalidating the leftmost index of the deque pointing to the maximum, then we can simply pop from the left.

LC 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Given an array of integers nums and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit.


class Solution:
def longestSubarray(self, nums: List[int], limit: int) -> int:
n = len(nums)
dec_queue = deque() # monotonic deque (weakly decreasing) for the maximums
inc_queue = deque() # monotonic deque (weakly increasing) for the minimums
left = ans = 0

for right in range(n):
curr_num = nums[right]

# maintain the deque invariants
while dec_queue and nums[dec_queue[-1]] < curr_num:
dec_queue.pop()
while inc_queue and nums[inc_queue[-1]] > curr_num:
inc_queue.pop()

dec_queue.append(right)
inc_queue.append(right)

# update sliding window to ensure the window is valid
while left <= right and nums[dec_queue[0]] - nums[inc_queue[0]] > limit:
# remove possibly invalidated indexes from the deques once the window has shifted
if dec_queue[0] == left:
dec_queue.popleft()
if inc_queue[0] == left:
inc_queue.popleft()
left += 1

# update the answer with the length of the current valid window
ans = max(ans, right - left + 1)

return ans

We're not trying to find a "next" or "previous" anything. We need to somehow process all subarrays to find the longest one such that the absolute difference between any two elements in the subarray is less than or equal to limit. The absolute difference is biggest (and thus threatens to exceed limit) when we take the difference between the subarray's maximum and its minimum. Hence, we're essentially trying to maintain a subarray's maximum and minimum. The previous practice problem, LC 239. Sliding Window Maximum, showed how to artfully handle maintaining a sliding window maximum. We employ similar logic here to maintain a sliding window maximum and minimum. Two deques are needed in order to do this effectively.

LC 496. Next Greater Element I

You are given two integer arrays nums1 and nums2 both of unique elements, where nums1 is a subset of nums2.

Find all the next greater numbers for nums1's elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, return -1 for this number.


class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
queries = {}
stack = []

# determine "next greater" values in nums2
for i in range(len(nums2)):
val_B = nums2[i]
while stack and nums2[stack[-1]] < val_B:
idx_val_A = stack.pop()
val_A = nums2[idx_val_A]
queries[val_A] = val_B
stack.append(i)

# remaining values have no next greater value (default to -1)
while stack:
idx_val_A = stack.pop()
val_A = nums2[idx_val_A]
queries[val_A] = -1

# the queries hash map tells us the next greater value
# for each value queried from nums1
ans = [None] * len(nums1)
for i in range(len(nums1)):
ans[i] = queries[nums1[i]]

return ans

The framing for this problem is somewhat odd at first. Nonetheless, once we can wrap our heads around what exactly is being asked, our approach is almost a direct application of the template for next value problems (specifically next greater value, of course). The code above can be cleaned up a little by using defaultdict from the collections module and not adhering so closely to the syntax of the template:

class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
queries = defaultdict(lambda: -1)
stack = []

for i in range(len(nums2)):
val_B = nums2[i]
while stack and nums2[stack[-1]] < val_B:
idx_val_A = stack.pop()
val_A = nums2[idx_val_A]
queries[val_A] = val_B
stack.append(i)

ans = [None] * len(nums1)
for i in range(len(nums1)):
ans[i] = queries[nums1[i]]

return ans
LC 503. Next Greater Element II

Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.

The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.


class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [None] * n
stack = []

for i in range(n * 2):
val_B = nums[i % n]
while stack and nums[stack[-1]] < val_B:
idx_val_A = stack.pop()
ans[idx_val_A] = val_B

# only add elements to the stack on the first full pass
if i < n:
stack.append(i)
else:
# otherwise the remaining values (if there are any)
# never had a next greater element; hence, we simply
# make another full pass to see if any element is greater
# than the current element in the stack and then pop the
# element from the stack if the answer is affirmative
if stack and nums[stack[-1]] < nums[i % n]:
idx_val_A = stack.pop()
ans[idx_val_A] = nums[i % n]

# the remaining values in the stack are those that do not have a next
# greater element despite two full passes; we report -1 for these values
while stack:
idx_val_A = stack.pop()
ans[idx_val_A] = -1

return ans

This problem is the same as LC 496. Next Greater Element I, but there's a significant twist where now we're considering the array to be circular. This may sound wild at first, but the change in approach is actually quite simple: we can cycle back through the original array by iterating a total of 2 * n times where n = len(nums). To ensure we don't get an "index out of bounds" error, we use a standard trick, namely the modulus operator %: i % n. Hence, if n = 10, and i = 10, then we're really looking at the element at index i = 0 since 10 % 10 == 0.

The approach above is a slightly tweaked application of the template for next value problems.

LC 901. Online Stock Span

Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock's price for the current day.

The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price.

For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].


Approach 1 (conventional approach for finding previous larger value; recommended)
class StockSpanner:
def __init__(self):
self.stack = []
self.idx = 0

def next(self, price: int