Monotonic

Monotonic: (of a function or quantity) varying in such a way that it either never decreases or never increases.

A monotonic stack or queue is one whose elements are always sorted. It can be sorted either ascending or descending.

Monotonic stacks and queues maintain their sorted property by removing elements that would violate the property before adding new elements.

By maintaining the sorted property, the search space is reduced.

Pseudocode for maintaining a monotonic increasing stack over an input array:

1
2
3
4
5
6
7
// Given an integer array nums
stack = []
for num in nums:
    while stack.length > 0 AND stack.top >= num:
        stack.pop()
    // Between the above and below lines, do some logic depending on the problem
    stack.push(num)

Despite the nested loop, the time complexity is still $O(n)$, where $n$ is the length of the array, because the inner while loop can only iterate over each element once across all for loop iterations, making the for loop iterations amortized $O(1)$.

Monotonic stacks and queues are useful in problems that, for each element, involves finding the “next” element based on some criteria, for example, the next greater element. They’re also good when you have a dynamic window of elements and you want to maintain knowledge of the maximum or minimum element as the window changes.

Problems

Problems#

Medium#

Hard#

Easy#

Problems

Medium

Hard

Easy