Skip to main content

Monotonic Structures Pattern

Imagine you are building a real‑time monitoring platform that tracks the CPU utilisation of thousands of servers. Your dashboard needs to display the maximum CPU usage over the last 5 minutes for each server, updated every second. Every time a new metric arrives, you must answer: “What is the maximum value among the last 300 data points?”

A naive implementation would scan the last 300 points for every server, every second. With 10,000 servers, that is 3 million operations per second — quickly overwhelming your system. You need a way to maintain the answer incrementally, without repeatedly scanning the window.

This is where monotonic structures come to the rescue. By maintaining a data structure that preserves a strict ordering of elements, we can eliminate useless candidates and keep only the information that matters for future queries.

Monotonic structures — both stacks and queues — embody a powerful engineering principle: do not repeatedly search for answers; maintain the information needed for future decisions. They appear in everything from trading systems that track price extrema to stream processing engines that compute sliding aggregates.

In this guide, we will explore monotonic stacks and queues as reusable algorithmic tools. You will learn how they work, why they achieve linear time complexity, and how to recognise opportunities to apply them in real‑world systems.

What Are Monotonic Structures?​

A monotonic structure is a data structure (stack or queue) that maintains its elements in a specific ordered sequence — either strictly increasing or strictly decreasing. The key invariant is:

For any two elements in the structure, their order reflects their values in a consistent direction.

Two Variants​

TypeOrder (bottom-to-top or front-to-back)Purpose
Monotonic IncreasingValues strictly increaseFind next smaller / previous smaller elements; maintain minimum candidates
Monotonic DecreasingValues strictly decreaseFind next greater / previous greater elements; maintain maximum candidates

The Invariant​

When a new element arrives, we remove elements that violate the monotonic order before inserting the new one. This removal step is the heart of the technique: it discards elements that can never become useful for future queries because the new element is both more recent and more extreme.

This automatic pruning is what transforms naive O(n²) algorithms into elegant O(n) solutions.

The Core Engineering Idea​

The Problem with Repeated Searching​

Consider the next greater element problem: given an array, for each element, find the first larger element to its right.

Naive approach: For each element, scan to the right until you find a larger value.

arr = [2, 1, 3, 4]

For 2: scan 1, 3 → found 3
For 1: scan 3 → found 3
For 3: scan 4 → found 4
For 4: none

Worst‑case: [5, 4, 3, 2, 1] — each element scans to the end → O(n²).

The Monotonic Insight​

Instead of scanning forward for each element, we can process the array from right to left and maintain a monotonic decreasing stack of candidates. For each element, we pop all smaller or equal elements from the stack. The top of the stack, if any, is the next greater element. We then push the current element.

Why does this work? Because when we encounter a larger element, it dominates all smaller elements that came after it — those smaller elements will never be the “next greater” for any earlier element.

Comparison of Approaches​

The monotonic approach processes each element once (push) and at most once (pop), yielding O(n) total time.

Part 1: Monotonic Stack

What Is a Monotonic Stack?​

A monotonic stack is a stack that maintains its elements in either increasing or decreasing order. The invariant is enforced during every push operation:

  • Monotonic Increasing Stack: Before pushing a new element x, pop all elements greater than x (so the stack remains increasing).
  • Monotonic Decreasing Stack: Before pushing x, pop all elements smaller than x (so the stack remains decreasing).

Why a Stack?​

A stack is ideal when we need to process elements in a last‑in‑first‑out (LIFO) manner. In many problems — like finding the next greater element — the most recent candidate is the most relevant. When a new, more extreme element arrives, it invalidates a contiguous block of previous candidates, which naturally aligns with stack popping.

Monotonic Increasing Stack​

Invariant: Values increase from bottom to top: bottom < ... < top.

When to Use​

  • Finding the previous smaller or next smaller element.
  • Maintaining a running minimum in a stream.
  • Problems like largest rectangle in histogram.

Example: Previous Smaller Element​

Given an array, for each element, find the nearest element to its left that is smaller.

Algorithm (left to right, increasing stack):

stack = []
for each x in arr:
    while stack and stack.top >= x:
        stack.pop()
    previous_smaller = stack.top if stack else -1
    stack.push(x)

Why It Works​

When we encounter x, any element in the stack that is >= x can never be the previous smaller for x or any future element (because x is more recent and smaller). So we pop them. The remaining top is the nearest smaller.

Monotonic Decreasing Stack​

Invariant: Values decrease from bottom to top: bottom > ... > top.

When to Use​

  • Finding the previous greater or next greater element.
  • Maintaining a running maximum in a stream.
  • Problems like stock span and daily temperatures.

Example: Next Greater Element​

Given an array, for each element, find the first larger element to its right.

Algorithm (right to left, decreasing stack):

stack = []
for each x in reversed(arr):
    while stack and stack.top <= x:
        stack.pop()
    next_greater = stack.top if stack else -1
    stack.push(x)

Why It Works​

Processing from right to left, we maintain candidates that are to the right of the current element. When x arrives, any candidate that is <= x is dominated by x (since x is further left and larger) and can never be the next greater for any earlier element. We pop them. The remaining top is the closest greater to the right.

Common Monotonic Stack Patterns​

1. Next Greater Element​

Problem: For each element, find the first element to the right that is greater.

Approach: Decreasing stack, right-to-left.

Variants:

  • Next Greater Element II (circular array): extend the array conceptually.
  • Next Greater Element with distance: store indices to compute distances.

2. Next Smaller Element​

Problem: For each element, find the first element to the right that is smaller.

Approach: Increasing stack, right-to-left (pop while >= current).

3. Previous Greater / Smaller​

Process left-to-right instead of right-to-left.

4. Largest Rectangle in Histogram​

Problem: Given a histogram (array of bar heights), find the largest rectangle that can be formed.

Approach: Use a monotonic increasing stack of indices. For each bar, we want to know the nearest smaller bar to its left and right. The stack helps compute these boundaries in O(n).

Why it works: The stack maintains indices with increasing heights. When we encounter a bar smaller than the stack top, we pop the top and compute the area where that popped bar is the shortest — its boundaries are determined by the new top (left) and the current index (right).

5. Daily Temperatures​

Problem: Given daily temperatures, for each day, find how many days to wait for a warmer temperature.

Approach: Decreasing stack of indices. When a warmer temperature arrives, we can pop all colder days and compute the difference in indices.

6. Stock Span​

Problem: For each day, compute the number of consecutive days (including today) with stock price ≤ today's price.

Approach: Decreasing stack of (price, span). Pop while stack top ≤ current price, accumulating spans.

Part 2: Monotonic Queue

What Is a Monotonic Queue?​

A monotonic queue is a deque (double‑ended queue) that maintains its elements in increasing or decreasing order. It is used specifically for sliding window problems where elements enter from one end and expire from the other.

Key Operations​

  1. Push (enqueue): Add a new element to the back. Before adding, pop all elements from the back that violate the monotonic order (just like the stack).
  2. Pop (dequeue): Remove elements from the front when they expire (fall out of the window).
  3. Get optimal: The front of the queue always holds the maximum (decreasing queue) or minimum (increasing queue) in the current window.

Why a Deque?​

We need to remove from both ends:

  • Back: to maintain order (pop worse candidates).
  • Front: to remove expired elements.

A deque supports O(1) operations on both ends.

Sliding Window Maximum​

The classic problem that showcases monotonic queues: given an array and a window size k, find the maximum value in each window.

Naive approach: For each window, scan all k elements → O(n·k).

Monotonic queue approach: O(n).

Algorithm​

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # stores indices, values in decreasing order
    result = []

    for i, x in enumerate(nums):
        # 1. Remove expired indices (outside window)
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # 2. Remove worse candidates from back
        while dq and nums[dq[-1]] <= x:
            dq.pop()

        # 3. Add current index
        dq.append(i)

        # 4. Record maximum (front of deque) when window is full
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

Visual Walkthrough​

Array: [1, 3, -1, -3, 5, 3, 6, 7], k = 3

Why Each Element Is Processed Once​

Each index is pushed once and popped at most once. Therefore, total time is O(n). This is a classic example of amortized analysis — even though individual operations may involve loops, over the entire run, the total work is linear.

Monotonic Queue Operations in Detail​

1. Remove Expired Elements​

while dq and dq[0] < i - k + 1:
    dq.popleft()

This ensures that only indices within the current window remain. Since indices are added in increasing order, the front of the deque is always the oldest.

2. Remove Worse Candidates​

while dq and nums[dq[-1]] <= x:
    dq.pop()

For a decreasing queue (max query), any element in the back that is ≤ the new element is dominated. Since the new element is more recent (will stay in the window longer) and has a larger value, the old element can never be the maximum for any future window. So we discard it.

3. Add New Candidate​

dq.append(i)

The new element is always added (it might become the maximum later).

4. Read Optimal Value​

nums[dq[0]]

The front holds the maximum (for decreasing queue) because we maintain decreasing order from front to back.

Monotonic Stack vs Monotonic Queue​

FeatureMonotonic StackMonotonic Queue
Primary structureStack (LIFO)Deque (double‑ended)
Element removalFrom top only (back)From both front (expiry) and back (order)
Expiration conceptNot typically usedEssential (sliding window)
Common problemsNext greater/smaller, histogram area, stock spanSliding window max/min, moving averages
Direction of processingOften left-to-right or right-to-leftAlways left-to-right (streaming)
Time complexityO(n) per passO(n) per pass

When to Choose Which​

  • Use a Monotonic Stack when you need to find the nearest element that satisfies a condition (to the left or right). The lack of expiry means you're looking for relationships between elements, not bounded by a window.
  • Use a Monotonic Queue when you need to maintain the best value over a sliding window where elements naturally expire.

Complexity Analysis​

Time Complexity: O(n)​

Both monotonic stack and queue algorithms process each element once for insertion and at most once for removal. The total number of iterations of the inner while loop across the entire run is bounded by n.

Space Complexity: O(n)​

In the worst case, the structure can hold all n elements (e.g., a strictly increasing array in an increasing stack).

Amortized Analysis​

The term amortized means we average the cost over a sequence of operations. Although a single while loop might pop many elements, each element is popped only once, so the total number of pops across all operations is ≤ n. Thus, the average cost per element is O(1).

👉 Related: For a deeper understanding, see our Amortized Analysis guide.

Monotonic Structures vs Other Patterns​

Sliding Window​

Sliding window and monotonic queue are often used together. The sliding window defines the scope; the monotonic queue maintains the optimal value within that scope.

Two Pointers​

Two pointers often maintain a window for condition‑based problems (e.g., subarray sum). Monotonic structures are used when the condition involves ordering (e.g., maximum in window) rather than a simple aggregate.

Prefix Sum​

  • Prefix Sum: Precomputes cumulative values to answer arbitrary range queries in O(1).
  • Monotonic Structures: Maintain ordered candidates to answer extremum queries in a moving stream without preprocessing the entire array.

Heap​

  • Heap: Maintains global order; useful when we need the top k elements or when elements have arbitrary priorities.
  • Monotonic Structures: Exploit local ordering in a sequence; they are more space‑efficient for sliding window extrema (O(k) vs O(n) for a heap of all elements).
PatternQuery TypeUpdate CostSpace
HeapGlobal min/max among all elementsO(log n)O(n)
Monotonic QueueLocal min/max in sliding windowO(1) amortizedO(k)
Prefix SumRange sumO(1) after O(n) preprocO(n)

Engineering Applications​

1. Real‑Time Monitoring​

Scenario: You need to display the peak CPU usage, latency, or error rate over the last N seconds.

  • Each new data point arrives with a timestamp.
  • Use a monotonic decreasing queue of (timestamp, value) to maintain the maximum.
  • As time advances, remove expired entries from the front.
  • The front of the queue gives the peak instantly.

Why it scales: O(1) per data point, no scanning of the entire time window.

2. Time‑Series Databases​

Scenario: InfluxDB, Prometheus, or custom TSDBs often need to compute downsampled aggregates (max, min, avg) over time windows.

  • For max/min, monotonic queues are used internally to compute windowed aggregates without re‑scanning.
  • For averages, prefix sums or exponential smoothing are often used, but extrema queries rely on monotonic structures.

Scenario: A stream processor computes the maximum value in a tumbling/sliding window.

  • Flink's windowed aggregations can use monotonic queues to compute incremental max/min.
  • For high‑throughput streams, this avoids O(window_size) processing per event.

4. Trading Systems​

Scenario: A high‑frequency trading system tracks the highest bid or lowest ask over the last N ticks.

  • Monotonic queues maintain extrema efficiently.
  • Also used in price trend analysis: find the highest price since a certain point.

5. Scheduling and Optimisation​

Scenario: An optimisation engine needs to repeatedly select the best candidate from a sliding window (e.g., job scheduling with deadlines).

  • Use a monotonic queue to maintain jobs ordered by priority within a time window, removing expired jobs.

6. Network Traffic Analysis​

Scenario: Detect bursts in network traffic by computing the maximum packet rate over a sliding window.

  • Monotonic queues allow real‑time burst detection with low overhead.

Common Mistakes​

1. Wrong Ordering Direction​

Using increasing when you need decreasing, or vice versa. Always ask: “Am I looking for max (decreasing queue) or min (increasing queue)?”

2. Forgetting to Remove Expired Elements​

In monotonic queues, forgetting to remove expired indices from the front leads to stale values in the result.

3. Using Stack When Queue Is Needed​

For sliding window problems, you must use a deque because elements expire from the front. A stack cannot efficiently remove from the front.

4. Incorrect Comparison Operator​

Using < vs <= matters when handling duplicates. For <=, you pop equal values, keeping the newer index (which is beneficial because it expires later). For <, you keep older duplicates.

5. Not Storing Indices​

When you need to check expiration, you must store indices (or timestamps) in the structure, not just values.

6. Confusing Monotonic Structures with Sorting​

Monotonic structures do not sort the entire array — they maintain a local invariant by discarding elements. The remaining elements are not necessarily sorted globally; they are just ordered with respect to the current context.

Best Practices​

1. Define the Invariant Clearly​

Before coding, write down:

  • “The deque stores indices with strictly decreasing values.”
  • “The front is always the maximum in the window.”

This clarity prevents off‑by‑one errors.

2. Use Indices, Not Values​

Store indices to support expiration checks. Retrieve values via the original array.

3. Handle Duplicates Consistently​

Decide whether to pop on <= or <. For max queries, popping on <= keeps the newer element and is generally preferred.

4. Test with Small Examples​

Before deploying in production, test with arrays of length 1, 2, and all‑equal values to verify boundary conditions.

5. Document the Amortized Complexity​

In code comments, mention that although a loop pops multiple elements, each element is popped once, giving O(n) overall.

6. Recognise the Pattern Early​

When you see:

  • “Find the nearest greater/smaller”
  • “Sliding window maximum/minimum”
  • “Stock span” or “daily temperature”

Think monotonic structure immediately.

Visual Walkthrough​

1. Monotonic Stack — Next Greater Element​

2. Monotonic Queue — Sliding Window Maximum​

3. Candidate Elimination in Monotonic Queue​

Key Takeaways​

  • Monotonic structures maintain elements in increasing or decreasing order by discarding elements that can never become useful.
  • They embody the engineering principle: maintain only the information needed for future decisions.
  • Monotonic Stack solves nearest greater/smaller problems in O(n) using LIFO order.
  • Monotonic Queue solves sliding window extrema problems in O(n) using a deque with expiration.
  • Both achieve linear time through amortized analysis — each element is pushed once and popped at most once.
  • These structures appear in real‑world systems: monitoring dashboards, time‑series databases, stream processors, trading engines, and scheduling optimisers.
  • Recognising the pattern — “I need the best value in a moving window or the nearest ordered element” — is the key to applying them effectively.

As an engineer, mastering monotonic structures gives you a powerful tool for building performant, low‑latency systems that process streams of ordered data efficiently.

AlgorithmDevPro — Engineering Thinking for Algorithmic Systems.