Monotonic stacks and queues are specialized data structures that maintain elements in sorted (increasing or decreasing) order. They solve a specific class of problems — finding the next greater or smaller element, computing areas of histograms, and optimizing sliding window operations — in O(N) time instead of the naive O(N^2). This guide covers the patterns, implementations, and the most common interview problems.
Monotonic Stack: Core Concept
A monotonic stack maintains elements in strictly increasing or decreasing order from bottom to top. When pushing a new element, pop all elements that violate the monotonic property. Monotonic decreasing stack (bottom to top, largest to smallest): when you push element X, pop all elements smaller than X. The popped elements have found their “next greater element” — it is X. After processing all elements, remaining elements in the stack have no next greater element. This processes all N elements in O(N) total because each element is pushed and popped at most once. Template for next greater element: initialize an empty stack and result array (filled with -1). For each element from left to right: while the stack is not empty and the current element is greater than the stack top: pop the top, set result[popped_index] = current element. Push the current element (and its index) onto the stack. After the loop, all remaining stack elements have result = -1 (no next greater element exists).
Pattern 1: Next Greater/Smaller Element
Next Greater Element I: given two arrays nums1 (subset) and nums2 (full), for each element in nums1 find its next greater element in nums2. Build a monotonic decreasing stack on nums2 to compute next_greater for every element. Store results in a hash map. Look up each nums1 element. Time: O(N). Daily Temperatures: given daily temperatures, for each day find how many days until a warmer temperature. Monotonic decreasing stack of indices. When you find a warmer day, the difference between indices is the answer. Next Greater Element II (circular array): the array wraps around. Process the array twice (iterate 0 to 2N-1, use index % N). The second pass handles the wrap-around. Stock Span: for each day, find the number of consecutive previous days with price less than or equal to today. Monotonic decreasing stack of prices. When you push today price, pop all smaller prices — the span is the difference between today index and the new stack top index. These problems all share the same structure: “for each element, find the nearest element that is greater/smaller in a specific direction.”
Pattern 2: Largest Rectangle in Histogram
Given an array of bar heights, find the largest rectangle that can be formed. For each bar, the rectangle extends left and right as far as bars are at least as tall. The width is determined by the nearest shorter bar on each side. Monotonic increasing stack approach: iterate through bars. For each bar: while the stack is not empty and the current bar is shorter than the stack top: pop the top bar. The popped bar height is the rectangle height. The width extends from the new stack top + 1 to the current index – 1. Compute area = height * width. Track the maximum area. After iterating, process remaining stack elements (they extend to the end of the array). Time: O(N) — each bar is pushed and popped once. Maximal Rectangle in a 2D matrix: for each row, compute the histogram of consecutive 1s above (height[j] = matrix[i][j] == 1 ? height[j] + 1 : 0). Apply the largest rectangle in histogram algorithm to each row. The maximum across all rows is the answer. Time: O(rows * cols). This is a classic hard problem that becomes straightforward once you know the histogram algorithm.
Pattern 3: Monotonic Queue for Sliding Window
A monotonic queue (deque) maintains the maximum or minimum element in a sliding window efficiently. Sliding Window Maximum: given an array and window size K, return the maximum element in each window position. Naive: O(N*K). With a monotonic decreasing deque: maintain a deque of indices where the corresponding values are in decreasing order. For each new element: remove indices from the front that are outside the window (index = K. The deque maintains candidates for the left boundary in increasing order of prefix sum.
When to Use Monotonic Stack vs Queue
Use a monotonic stack when: (1) Finding the next/previous greater or smaller element. (2) Computing areas or spans based on boundaries defined by larger/smaller neighbors. (3) The problem involves comparing each element with its neighbors in one direction. Use a monotonic deque (queue) when: (1) Finding the maximum or minimum in a sliding window. (2) The problem involves a window that moves forward and you need the optimal element within the window. (3) Both ends of the data structure need modification (add at back, remove from front for window expiration, remove from back for monotonic property). Recognition signals: “next greater element,” “previous smaller element,” “maximum in every window of size K,” “largest rectangle,” “stock span,” and “daily temperatures” all indicate monotonic stack/queue. The key insight: the O(N) time comes from the amortized analysis — each element is pushed and popped at most once across the entire algorithm, even though there is a while loop inside the for loop.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is a monotonic stack and how does it solve next greater element problems?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A monotonic stack maintains elements in strictly increasing or decreasing order. When pushing a new element, pop all elements that violate the monotonic property. For next greater element: use a monotonic decreasing stack. Push elements from left to right. When the current element is greater than the stack top, pop the top — the current element IS the next greater element for the popped element. After processing, remaining stack elements have no next greater element. Why O(N): each element is pushed once and popped at most once across the entire algorithm. The while loop inside the for loop does not make it O(N^2) because the total pops across all iterations cannot exceed N. Template: stack = [], result = [-1] * N. For i in range(N): while stack and nums[i] > nums[stack[-1]]: popped = stack.pop(); result[popped] = nums[i]. stack.append(i).”}},{“@type”:”Question”,”name”:”How does the largest rectangle in histogram algorithm work?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”For each bar in the histogram, the largest rectangle using that bar height extends left and right until hitting a shorter bar. The width is bounded by the nearest shorter bars on each side. Monotonic increasing stack approach: iterate through bars. For each bar: while the stack is not empty and current bar is shorter than stack top: pop. The popped bar height is the rectangle height. Width = (current_index – new_stack_top – 1). Area = height * width. Track maximum. Push current bar. After iteration, process remaining stack (they extend to the end). Time: O(N). This extends to 2D: Maximal Rectangle in a binary matrix. For each row, compute histogram heights (consecutive 1s above). Apply the histogram algorithm per row. The maximum across all rows is the answer. Time: O(rows * cols).”}},{“@type”:”Question”,”name”:”How does a monotonic deque solve sliding window maximum in O(N)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Maintain a deque of indices where corresponding values are in decreasing order (front = largest). For each new element: (1) Remove indices from the front that are outside the window (index monotonic stack. Maximum/minimum in every window of size K -> monotonic deque. Largest rectangle or area bounded by heights -> monotonic stack. The key insight for both: each element is processed at most twice (pushed once, popped once), giving O(N) total time despite nested loops.”}}]}