Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 63 ยท Data Structures in Contest Practice

Monotonic Stacks, Heaps and Deques in Contests

Contest patterns for monotonic stacks, sliding window maximum with a deque, and priority queues with lazy deletion, each tested against brute force in Python.

Three small structures, the stack, the deque and the heap, solve a surprising share of contest problems when you use them in a disciplined way. The discipline is this: instead of storing everything you have seen, store only what can still matter. A monotonic stack keeps candidates in sorted order and throws away elements that can never be the answer. A monotonic deque does the same for a sliding window. A heap with lazy deletion lets you "remove" an item you cannot find by simply ignoring it when it surfaces.

Each of these turns an O(n^2) scan into O(n) or O(n log n). The theory of stacks and queues is in Monotonic Stack, Deque and Monotonic Queue and Heaps; in this lesson we apply them the way contests do, with attention to ties and to stress testing.

The monotonic stack

Problem: for each element of an array, find the nearest element to its right that is strictly greater (the next greater element). The brute force scans right from each position, O(n^2) in the worst case.

Walk left to right and keep a stack of indices whose values are decreasing from bottom to top. These are the elements still waiting for a greater one. When a new value a[i] arrives, every stack element smaller than it has just found its answer: pop them and record i as their next greater index. Then push i. Each index is pushed once and popped at most once, so the total work is O(n) even though there is a loop inside the loop.

flowchart TD
    A["New value a[i]"] --> B{"Stack top smaller than a[i]?"}
    B -->|yes| C["Pop it: its answer is i"]
    C --> B
    B -->|no| D["Push i"]

Every index is pushed once and popped at most once, so the loop is linear.

The same skeleton, with the comparison flipped, finds the previous smaller element, the next smaller element and so on. Memorize one version and change the sign.

Two classic uses:

  • Largest rectangle in a histogram. For each bar, the widest rectangle using its full height extends to the nearest smaller bar on each side. Find both with one stack pass.
  • Sum of subarray maximums. For each element, count the subarrays in which it is the maximum: (i - left) * (right - i), where left and right are the nearest blocking positions. Ties need a rule so that a subarray with two equal maxima is counted once: use >= on one side and > on the other.
Python Next greater element, histogram and subarray maxima

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The monotonic deque: sliding window maximum

Now ask for the maximum of every window of length k. Keep a deque of indices whose values are decreasing from front to back. For each new index i:

  1. Pop from the back while the back value is not larger than a[i]. Those elements are older and smaller, so they can never be a window maximum again.
  2. Push i at the back.
  3. If the front index has fallen out of the window (front <= i - k), pop it from the front.
  4. Once i >= k - 1, the front is the maximum of the current window.

Use collections.deque; list.pop(0) is O(n) and will turn the solution quadratic. The same structure powers DP speedups such as "dp[i] = a[i] + max of dp over the previous k positions" (see DP Speedups).

Heaps and lazy deletion

heapq is a min-heap. For a max-heap, push negated values. It supports push and pop-min in O(log n) but has no way to remove an arbitrary item. Instead of searching the heap, mark the item as deleted and discard it when it reaches the top:

  • Keep a Counter of values that are pending deletion.
  • To delete x, increment pending[x] (and the live count for bookkeeping).
  • Before reading the top, pop while the top has a pending deletion, decrementing the counter.

Each item is pushed once and popped once, so the amortized cost per operation stays O(log n). The typical interface is a "dynamic multiset" with add, remove and max, which is exactly what a sliding window over a stream needs when you cannot use a monotonic deque (for example when the removal order is arbitrary).

A second heap trick is the two-heap median: a max-heap for the lower half and a min-heap for the upper half, kept balanced in size. Deletions again use lazy marking.

Python Sliding window maximum and a lazy-deletion heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Which tool when?

Question Tool
Nearest greater/smaller on the left or right Monotonic stack
Max/min of every window of fixed length Monotonic deque
Max/min with arbitrary insert and delete Heap with lazy deletion (or a balanced tree)
k largest or smallest items overall Heap of size k, or heapq.nlargest
Always process the smallest pending item next Plain heapq
First in, first out deque, never list.pop(0)

Pitfalls

  • Ties. Decide strictly-greater versus greater-or-equal before coding and write it in a comment. Mixed conventions on the two sides is correct for counting (each subarray assigned to exactly one maximum); the same convention on both sides double-counts.
  • Stack of indices, not values. You almost always need the position later, and the value is a[idx].
  • Sentinels. Appending 0 to the histogram avoids a second loop to flush the stack.
  • Heap of tuples. Python compares tuples element by element, so equal first elements fall through to the second; make sure the second is comparable (use a counter as a tiebreaker if it holds objects).
  • Forgetting that heapq is a min-heap. Negate for max, and negate back when reading.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is the monotonic stack algorithm O(n) even though it has a while loop inside a for loop?

    Total pops cannot exceed total pushes, which is n. The amortized cost per element is therefore constant.
  2. 2. In a sliding window maximum with a deque of indices, which condition removes the front?

    The front is the oldest index. Once it is at least k positions behind i, it is outside the current window and must go.
  3. 3. How do you emulate a max-heap with Python's heapq?

    heapq only implements a min-heap. The smallest negated value is the largest original value.
  4. 4. What does lazy deletion do?

    An item that is buried in the heap cannot be removed cheaply. Marking it and skipping it when it surfaces keeps every operation O(log n) amortized.
  5. 5. When counting subarrays by their maximum element, why use >= on one side and > on the other?

    If both sides were strict or both non-strict, subarrays containing equal maxima would be counted several times or not at all.

Summary

  • A monotonic stack finds nearest greater/smaller elements in O(n); keep indices, not values.
  • Largest rectangle in a histogram and sum of subarray maxima are two applications of one stack pass; handle ties asymmetrically.
  • A monotonic deque gives the maximum of every fixed-length window in O(n).
  • heapq is a min-heap; negate for a max-heap, and use lazy deletion when you cannot remove an arbitrary item.
  • Use deque for queues, and always test against a brute force on small random arrays with many ties.

Next: DSU and Tree Problems