Monotonic Stack Concept
A monotonic stack maintains elements in strictly increasing or decreasing order. Elements that violate the order are popped before the new element is pushed. This gives O(n) solutions for problems that ask about the nearest element that is greater/smaller, largest rectangle in a range, or span of dominance. Key pattern: while stack and new element violates the order, pop and process the popped element using the relationship to the new element. Each element is pushed and popped at most once: O(n) total.
Next Greater Element (LC 496, 503)
For each element, find the next element to the right that is greater. Monotonic decreasing stack: iterate left to right. For each nums[i]: while stack and nums[stack.top()] < nums[i]: result[stack.pop()] = nums[i]. Push i. Elements remaining in the stack after the pass have no next greater element (result = -1). Circular array variant (LC 503): iterate twice (0 to 2n-1), using index mod n. O(n) time, O(n) space for the stack and result array.
def next_greater(nums):
n = len(nums)
result = [-1] * n
stack = [] # stores indices
for i in range(n):
while stack and nums[stack[-1]] < nums[i]:
result[stack.pop()] = nums[i]
stack.append(i)
return resultLargest Rectangle in Histogram (LC 84)
For each bar, the widest rectangle with that bar as the shortest bar extends left until a shorter bar and right until a shorter bar. Monotonic increasing stack: maintain indices of bars in increasing height order. For each bar i: while stack and heights[stack.top()] > heights[i]: pop index j. The width = i – stack.top() – 1 (if stack non-empty) or i (if stack empty). Area = heights[j] * width. Update max area. Push i. After the loop: process remaining stack with right boundary = n. O(n) time, O(n) space. Trick: append 0 at the end to flush the stack at the end automatically.
Daily Temperatures (LC 739)
For each day, find the number of days until a warmer temperature. Same pattern as next greater element, but store the distance instead of the value. Monotonic decreasing stack of indices: for each day i: while stack and temperatures[stack.top()] < temperatures[i]: j = stack.pop(); result[j] = i – j. Push i. O(n) time. The stack always contains days waiting for their first warmer day; they are processed (popped) as soon as a warmer day arrives.
Sliding Window Maximum (LC 239)
Find the maximum of each sliding window of size k. Naive: O(n*k). With a monotonic deque (double-ended queue): maintain a deque of indices in decreasing value order. Invariant: deque front always has the maximum of the current window. For each i: (1) Remove indices from the front that are outside the window (index < i-k+1). (2) Remove indices from the back while their values are less than nums[i] (they can never be the maximum — a larger element is now in the window). (3) Append i to the back. (4) The front of the deque is the index of the current window maximum. O(n) time — each element is added and removed from the deque at most once.
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, num in enumerate(nums):
while dq and dq[0] < i - k + 1:
dq.popleft()
while dq and nums[dq[-1]] = k - 1:
result.append(nums[dq[0]])
return resultSum of Subarray Minimums (LC 907)
Sum of minimum of every subarray. For each element arr[i], find how many subarrays have arr[i] as their minimum. Left boundary: the nearest index l where arr[l] < arr[i]. Right boundary: the nearest index r where arr[r] <= arr[i] (strict on one side to avoid double-counting equal elements). Number of subarrays where arr[i] is the minimum = (i – l) * (r – i). Contribution = arr[i] * (i – l) * (r – i). Compute left and right boundaries with two monotonic stack passes, or one combined pass. O(n) time. LC 2104 (sum of subarray ranges) extends this to sum of (max – min) for all subarrays.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is a monotonic stack and why is it O(n)?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “A monotonic stack is a stack that maintains elements in either strictly increasing or strictly decreasing order. When a new element violates the order, elements are popped until the order is restored, then the new element is pushed. It is O(n) total because each element is pushed exactly once and popped at most once — a total of at most 2n operations across the entire traversal. The key insight: the monotonic stack processes elements that are no longer useful. For next greater element: once a greater element arrives, all smaller elements waiting in the stack are resolved and can be popped. They will never be the answer for any future query because the current element is greater and more recent.”
}
},
{
“@type”: “Question”,
“name”: “How do you solve the largest rectangle in histogram problem?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “For each bar, the maximum rectangle using that bar as the shortest bar extends left until the first bar shorter than it and right until the first bar shorter than it. A monotonic increasing stack finds these boundaries efficiently. Iterate left to right: for each bar i, while the stack top j has height > heights[i], pop j and compute the rectangle: width = i – stack.top() – 1 if the stack is non-empty, else width = i. Area = heights[j] * width. Update the global max. Push i. After the loop, process remaining stack elements with right boundary = n. Append a sentinel bar of height 0 to flush the stack at the end. O(n) time, O(n) space. LC 84. LC 85 (Maximal Rectangle) reduces to calling this on each row of the grid.”
}
},
{
“@type”: “Question”,
“name”: “How does the monotonic deque solve the sliding window maximum problem?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “The sliding window maximum asks for max(nums[i-k+1 .. i]) for each window position i. A naive approach iterates over the window: O(nk). A monotonic decreasing deque (max-deque) gives O(n). Invariant: the deque stores indices in decreasing order of their values; the front is always the index of the current window maximum. For each new index i: (1) Remove expired indices from the front (index = nums[i] (they cannot be the nearest smaller to the left for anything to the right — nums[i] is smaller and closer). The top of the stack after popping is the nearest element smaller than nums[i] to the left. If the stack is empty: no smaller element to the left (result = -1 or 0). Push nums[i] (or index i). O(n) time. Variation table: nearest greater to right -> monotonic decreasing stack, iterate left to right. Nearest greater to left -> monotonic decreasing stack, iterate right to left. Nearest smaller to right -> monotonic increasing stack, iterate left to right. Nearest smaller to left -> monotonic increasing stack, iterate right to left.”
}
},
{
“@type”: “Question”,
“name”: “How do you compute the sum of subarray minimums using a monotonic stack?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “The sum of minimums of all subarrays equals the sum over all elements of (element value * number of subarrays where it is the minimum). For each element arr[i], count subarrays where arr[i] is the minimum: left_span = i – left_boundary (number of ways to extend left), right_span = right_boundary – i (ways to extend right). Contribution = arr[i] * left_span * right_span. Boundaries: left_boundary = index of nearest element STRICTLY LESS than arr[i] (use strict < on one side, <= on the other to avoid double-counting equal elements). Use a monotonic stack to compute all left boundaries in O(n) and all right boundaries in O(n). Sum all contributions mod 10^9+7 (LC 907). O(n) time, O(n) space. Extension: sum of (max – min) for all subarrays = sum of subarray maxima – sum of subarray minima (LC 2104)."
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Twitter/X Interview Guide