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.
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Twitter/X Interview Guide