Monotonic stack and deque

Many problems ask you to find the next element larger than the current one, or track the maximum value over a sliding window. Checking every candidate directly is $O(N^2)$. A monotonic stackmonotonic stackA stack storing elements in monotonic order, used to efficiently find the next greater element.In the glossary or monotonic dequemonotonic dequeA double-ended queue maintaining elements in monotonic order to track sliding window maximum.In the glossary answers these questions in $O(N)$ by discarding elements the moment they can no longer be part of any future answer.

Next greater element with a monotonic stack

For each position in an array, you want the index of the next element that is larger than it. A direct scan from every position costs $O(N^2)$. A monotonic stack does it in $O(N)$ instead.

The stack holds indices, not values, and it maintains an invariant: the values at those indices increase from bottom to top. When a new element arrives, pop every index whose value is smaller (each of those indices just found its next greater element, the current one), then push the current index.

1import sys2
3
4def main() -> None:5    input_data = sys.stdin.read().split()6    n = int(input_data[0])7    arr = list(map(int, input_data[1:n + 1]))8
9    result = [-1] * n10    stack = []11
12    for i in range(n):13        while stack and arr[stack[-1]] < arr[i]:14            result[stack.pop()] = i15        stack.append(i)16
17    print("\n".join(map(str, result)))18
19
20if __name__ == "__main__":21    main()

6
2 1 3 4 2 3

2
2
3
-1
5
-1

Walk through [2, 1, 3, 4, 2, 3]. At index 0, the stack is empty, so push 0. At index 1, arr[1] = 1 is smaller than arr[0] = 2, so push 1 without popping. At index 2, arr[2] = 3 is larger than arr[1] = 1, so pop 1 and record result[1] = 2; it is also larger than arr[0] = 2, so pop 0 and record result[0] = 2; the stack is now empty, so push 2. At index 3, arr[3] = 4 is larger than arr[2] = 3, so pop 2 and record result[2] = 3, then push 3. At index 4, arr[4] = 2 is smaller than arr[3] = 4, so push 4 without popping. At index 5, arr[5] = 3 is larger than arr[4] = 2, so pop 4 and record result[4] = 5; it is not larger than arr[3] = 4, so push 5. At the end, the indices still on the stack, 3 and 5, never found a next greater element, so their results stay -1. The final answer is [2, 2, 3, -1, 5, -1], matching the program's output. Every index is pushed exactly once and popped at most once, so the total work across the whole scan is $O(N)$, even with a loop inside the loop.

Sliding window maximum with a monotonic deque

A sliding window maximum problem asks for the largest value in every consecutive window of size K. In [1, 3, 1, 2, 0, 5] with K = 3, the windows [1, 3, 1], [3, 1, 2], [1, 2, 0], and [2, 0, 5] have maximums 3, 3, 2, 5.

A monotonic deque keeps indices in decreasing order of value. When a new element enters, remove indices from the back while their values are smaller or equal (they can never be the maximum again once a later, larger value exists), then push the new index. When the index at the front falls outside the window, remove it too. The front of the deque is always the current window's maximum.

1import sys2from collections import deque3
4
5def main() -> None:6    input_data = sys.stdin.read().split()7    n = int(input_data[0])8    k = int(input_data[1])9    arr = list(map(int, input_data[2:2 + n]))10
11    dq = deque()12    result = []13
14    for i in range(n):15        # Remove indices outside the window16        while dq and dq[0] < i - k + 1:17            dq.popleft()18
19        # Remove indices of elements smaller than current20        while dq and arr[dq[-1]] <= arr[i]:21            dq.pop()22
23        dq.append(i)24
25        # The maximum in the current window is at the front26        if i >= k - 1:27            result.append(arr[dq[0]])28
29    print("\n".join(map(str, result)))30
31
32if __name__ == "__main__":33    main()

6 3
1 3 1 2 0 5

3
3
2
5

As with the stack, each index enters and leaves the deque at most once, so the total cost is $O(N)$. The deque only ever holds indices that could still be the maximum of some future window, which is a small fraction of all the indices seen so far.

Reusing the deque for a feasibility check

The same sliding-window deque answers a different kind of question: has any value within the last K positions crossed a threshold? This is not a new data structure, it is the same monotonic deque from the previous section, read differently: instead of reporting the maximum directly, you compare the front of the deque against a fixed threshold at every step.

1import sys2from collections import deque3
4
5def main() -> None:6    input_data = sys.stdin.read().split()7    n = int(input_data[0])8    values = list(map(int, input_data[1:n + 1]))9
10    threshold = 5011    max_offset = 312
13    dq = deque()14    offset = 015    result = []16
17    for i in range(n):18        offset = max(0, i - max_offset)19
20        # Remove indices that are too old21        while dq and dq[0] < offset:22            dq.popleft()23
24        # Remove values smaller than current25        while dq and values[dq[-1]] <= values[i]:26            dq.pop()27
28        dq.append(i)29
30        # Check if max in range exceeds threshold31        if dq and values[dq[0]] >= threshold:32            result.append("yes")33        else:34            result.append("no")35
36    print("\n".join(result))37
38
39if __name__ == "__main__":40    main()

8
80 10 20 30 10 10 10 10

yes
yes
yes
yes
no
no
no
no

With values = [80, 10, 20, 30, 10, 10, 10, 10], a threshold of 50, and a window of the last 4 positions, the deque's front is 80 at first, so the answer is "yes" for as long as position 0 is still inside the window. Once the window has moved far enough that position 0 falls out of range, at position 4, the front becomes 30, which is under the threshold, so the answer flips to "no" and stays there, since nothing after position 0 reaches 50. Answering "is there ever a value above the threshold" without windowing would stay "yes" forever once 80 appears; the deque's job is exactly to forget values once they fall outside the window that still matters.

Why the invariant holds

A smaller element can never become the next greater element once a larger one appears after it. If index i holds value 5 and a later index j holds value 8, every position after j that looks backward for something larger finds 8 before it ever reaches 5. The value 5 becomes irrelevant the moment 8 appears, so the monotonic stack discards it immediately instead of carrying it forward. The same reasoning applies to the deque: once a larger value enters the window, every smaller value still inside the window can never again be the maximum, so removing it early costs nothing and saves the deque from growing without bound.

Common mistakes

Forgetting to pop from the back of a monotonic deque is the most common error. Only popping from the front, as values leave the window, leaves stale smaller entries behind, and the front is no longer guaranteed to be the maximum. If the deque holds indices with values [5, 3, 8] from front to back and a new value 7 arrives, both 5 and 3 must be popped from the back before 7 is added, since both are smaller than 7 and neither can ever be the answer again.

Another mistake is using a plain Python list with pop(0) where a collections.deque belongs. Removing the first element of a list is $O(N)$, since every remaining element shifts down by one; a deque gives $O(1)$ removal from both ends.

A third mistake is storing values instead of indices in a monotonic deque used for a sliding window. Values alone cannot tell you whether an entry has aged out of the window; only its original index can, which is why every example in this lesson stores indices and looks up the value through the array when it needs it.

Monotonic structures matter most once $N$ reaches $10^5$ or higher, where an $O(N^2)$ scan is too slow no matter how tightly the inner loop is written. Turning a windowed maximum or next-greater query into an amortized $O(1)$ operation per element is what keeps a senior-level solution inside the time limit.

Recap

A monotonic stack keeps indices with increasing values and finds the next greater element in $O(N)$. A monotonic deque keeps indices with decreasing values and tracks a sliding window's maximum in $O(N)$. The same deque, read against a fixed threshold instead of reported directly, answers a windowed feasibility check without any new machinery.