Stacks, Queues & Monotonicity

Stacks, Queues & Monotonicity | Algoryva

Implementation

The operations in code

The basic operations are tiny. Learn exactly what each returns.

python

from collections import deque

stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop())   # 3
print(stack[-1])   # 2

q = deque([1, 2, 3])
q.append(4)
print(q.popleft())   # 1
print(q[0])   # 2
print(list(q))   # [2, 3, 4]

Reading the code

›stack.pop() removes and returns the last item (3). stack[-1] only *looks* at the top without removing it (peek).
›q.popleft() removes and returns the front item (1), the one that has waited longest. q[0] peeks at the front.
›Popping from an empty stack or queue raises an error, so guard with if stack: / if q: when the structure might be empty.

Implementation

Matching brackets with a stack

Is ([]{}) correctly nested, and (] not? The most recently opened bracket must be the first one closed, which is exactly last in, first out.

Plan in plain steps

pseudocode

for each character:
    if it opens a bracket: push it
    if it closes one: the stack's top must be its matching opener, else fail; pop it
at the end the stack must be empty

python

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

print(is_valid("([]{})"))   # True
print(is_valid("(]"))   # False
print(is_valid("(("))   # False

Reading the code

›pairs maps each closer to the opener it needs.
›On a closer we need an opener waiting on top. not stack catches a closer with nothing open (like )), and the != check catches a wrong type (like (]).
›return not stack at the end catches leftover openers, such as in ((.

First, the naive way

Next greater element: compare with everything to the right

For each element of an array, find the first larger value somewhere to its right, or -1. The direct way scans right from every position.

If the array is decreasing, each element scans to the very end and finds nothing. Elements near the front re-read the same tail again and again.

python

def next_greater_naive(a):
    res = []
    for i in range(len(a)):
        ans = -1
        for j in range(i + 1, len(a)):
            if a[j] > a[i]:
                ans = a[j]
                break
        res.append(ans)
    return res

print(next_greater_naive([2, 1, 5, 3, 4, 6, 1]))   # [5, 5, 6, 4, 6, -1, -1]

Cost: O(n²). For n = 2 × 10^5 that is about 2 × 10^10 comparisons.

Worked by hand

Traced by hand

Array [2, 1, 5, 3, 4, 6, 1]. The stack holds values still waiting for a larger one (shown as indices in the code).

read	pops (answer found)	stack after push
2	none	2
1	none (2 is not less than 1)	2, 1
5	1 → 5, then 2 → 5	5
3	none	5, 3
4	3 → 4	5, 4
6	4 → 6, then 5 → 6	6
1	none	6, 1

1
Leftovers
After the last element, the stack still holds 6 and 1. Nothing bigger came after them, so their answer is -1.
2
Why it is O(n)
Every element is pushed exactly once and popped at most once. The inner while looks expensive, but across the whole run it pops at most n items.

Implementation

Monotonic stack in code

Store indices rather than values so you can write the answer into the right slot.

python

def next_greater(a):
    res = [-1] * len(a)
    stack = []                         # indices, values non-increasing
    for i, x in enumerate(a):
        while stack and a[stack[-1]] < x:
            res[stack.pop()] = x
        stack.append(i)
    return res

print(next_greater([2, 1, 5, 3, 4, 6, 1]))   # [5, 5, 6, 4, 6, -1, -1]

Reading the code

›res starts at -1, so anything never popped automatically keeps the right “no answer” value.
›a[stack[-1]] < x compares the waiting element on top with the new value. Use <= instead if “greater” should mean “greater or equal”.
›After popping everything smaller, push the current index: it now waits for its own bigger value.

Implementation

Sliding window maximum with a monotonic deque

For every window of size k, report the maximum. Keep a deque of indices whose values are decreasing. The front is always the current maximum. New elements remove smaller ones from the back (they can never be the maximum while the new one is in the window) and expired indices fall off the front.

python

from collections import deque

def window_max(a, k):
    dq, out = deque(), []
    for i, x in enumerate(a):
        while dq and a[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(a[dq[0]])
    return out

print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))   # [3, 3, 5, 5, 6, 7]

Reading the code

›The back of the deque is trimmed like a monotonic stack, so values decrease from front to back.
›dq[0] <= i - k drops the front index when it has slid out of the window.
›From i = k - 1 onward a full window exists, and a[dq[0]] is its maximum.
›Each index is added once and removed once, so the whole pass is O(n) even though the maximum changes.

Worked problem

Days until a warmer temperature

The problem

Given daily temperatures, return for each day how many days you must wait for a warmer day, or 0 if there is none.

This is “next greater element”, but we need the distance in days, not the value.
Use the same monotonic stack of indices. When day i is warmer than the waiting day j on top, the answer for j is i − j.
Anything left on the stack keeps the default 0.

python

def daily_temperatures(t):
    res = [0] * len(t)
    stack = []
    for i, x in enumerate(t):
        while stack and t[stack[-1]] < x:
            j = stack.pop()
            res[j] = i - j
        stack.append(i)
    return res

print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))   # [1, 1, 4, 2, 1, 1, 0, 0]

Takeaway. Storing indices (not values) is what lets one template answer both “what is the next greater value” and “how far away is it”.

Worked problem

Longest run of balanced brackets

The problem

Given a string of ( and ), return the length of the longest contiguous substring that is a correctly nested sequence.

Keep a stack of indices. Start with -1 on it as a base marker for “the position before the string”.
On (, push its index.
On ), pop. If the stack becomes empty, this ) has no partner, so push its index as the new base. Otherwise the current balanced run extends from the new top to here: length i − stack[-1].

python

def longest_valid(s):
    stack = [-1]
    best = 0
    for i, ch in enumerate(s):
        if ch == "(":
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                best = max(best, i - stack[-1])
    return best

print(longest_valid(")()())"))   # 4

Takeaway. Stacks of indices remember *where* unmatched items are, letting you measure lengths between them. The base marker -1 removes special cases.

Wrap-up

Remember this

A stack returns the newest item, a queue the oldest; choose by the order you need.
Python: list for a stack, deque for a queue or both ends.
Stacks match nested structure, and a monotonic stack answers “next greater” in O(n) because each element is pushed and popped once.
A monotonic deque keeps the maximum of a sliding window in O(n).
Store indices, guard against empty structures, and decide what leftovers mean.

Cheat sheet

Stack (LIFO): list: append, pop, [-1] to peek
Queue (FIFO): deque: append, popleft, [0] to peek
Monotonic stack: pop while top < x; answer for popped = x; push index
Window max: deque of decreasing values; drop expired from the front
Cost: each element pushed and popped once → O(n)
Never: list.pop(0) as a queue

Top traps to avoid

Using list.pop(0) for a queue.
Storing values in a monotonic stack when you need positions.
Forgetting to check the stack is empty before stack[-1] or pop().

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.Which structure returns items in the order they arrived (first in, first out)?
2.next_greater([2, 1, 5, 3]) returns:
3.Why is the monotonic stack O(n) despite a while loop inside a for loop?
4.“For each day, how many days until a warmer one?” is best solved with:
5.Why is list.pop(0) a poor queue in Python?
6.is_valid("(]") returns False. Which check catches it?
7.s = []; push 1, push 2, push 3; pop; push 4. What does print(s) show?
8.d = deque([1, 2, 3]); d.rotate(1). What is list(d)?
9.Next greater element for [2, 1, 2, 4, 3] using a monotonic stack (-1 when none). What is printed?
10.Is the string "([)]" a valid bracket sequence? Print the result of the stack check.
11.Why does a monotonic stack keep its items in order?
12.q = deque(); append 1, append 2; popleft(); print(q[0]). What is printed?
13.Push and pop on a list-based stack: what is the time per operation?
14.Why is a deque better than a list for a queue?
15.Daily temperatures [73, 74, 75, 71, 69, 72, 76, 73] with a monotonic stack: how many days until a warmer day for each? What is printed?

Stacks, Queues & Monotonicity

After this lesson you will be able to

Builds on

Unlocks

A stack of plates and a line at a shop

Stack, queue, deque

The operations in code

Reading the code

Matching brackets with a stack

Reading the code

Next greater element: compare with everything to the right

Once something finds its answer, forget it

The monotonic stack

Traced by hand

Monotonic stack in code

Reading the code

Sliding window maximum with a monotonic deque

Reading the code

Why these costs

Edge cases

Mistakes to avoid

How to spot stacks, queues and monotonic structures

Days until a warmer temperature

Longest run of balanced brackets

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up3 problems

Core20 problems

Application31 problems

Challenge6 problems