Monotonic Stack: Next Greater Element and Largest Rectangle
28 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Some questions ask about the nearest bigger or smaller item: the next higher price, the next warmer day. Checking to the right for every item is slow. A monotonic stack keeps the unanswered items and answers them in one pass.
Next greater element
Monotonic stack is a stack whose values stay in one order, rising or falling, from bottom to top. Before a new item is pushed, the items that break the order are popped.
For each price, find the next later price that is higher, or -1 if none. Checking every later price is O(n squared). A stack can wait for the answer instead.
The stack of waiting indexes
Keep the indexes that have not found a greater value yet. Their values fall from bottom to top. A new value pops every smaller waiting value and becomes their answer.
def next_greater(nums): result = [-1] * len(nums) stack = [] for i, value in enumerate(nums): while stack and nums[stack[-1]] < value: result[stack.pop()] = value stack.append(i) return resultExample 1 · Brute force: scan to the right
def next_greater_slow(nums): result = [] for i in range(len(nums)): found = -1 for j in range(i + 1, len(nums)): if nums[j] > nums[i]: found = nums[j] break result.append(found) return result
print(next_greater_slow([4, 5, 2, 25, 7]))[5, 25, 25, -1, -1]
What this code does
- For every item the inner loop searches to the right, so the time is O(n squared) and the extra space is O(n) for the result.
- The stack version in the next example does the same job in O(n).
Example 2 · Next greater with a monotonic stack
def next_greater(nums): result = [-1] * len(nums) stack = [] for i, value in enumerate(nums): while stack and nums[stack[-1]] < value: result[stack.pop()] = value stack.append(i) return result
print(next_greater([4, 5, 2, 25, 7]))print(next_greater([9, 7, 5]))[5, 25, 25, -1, -1] [-1, -1, -1]
What this code does
- The waiting indexes always hold values from large to small. 25 arrives and pops 2 and 5 in one go.
- A falling list such as
[9, 7, 5]never pops, so every answer is -1.
Example 3 · Trace the stack
nums = [4, 5, 2, 25, 7]stack = []for i, value in enumerate(nums): while stack and nums[stack[-1]] < value: print(value, "answers", nums[stack.pop()]) stack.append(i) print("stack values", [nums[k] for k in stack])stack values [4] 5 answers 4 stack values [5] stack values [5, 2] 25 answers 2 25 answers 5 stack values [25] stack values [25, 7]
What this code does
- Printing the waiting values shows the stack always falls from bottom to top.
- A bigger value is the answer for everything it pops.
Each index is pushed once and popped once, so the total work is O(n) even with a while inside a for. Indexes still waiting at the end keep -1.
Store indexes when you need distances
Daily temperatures ask how many days until a warmer day. The answer is a distance, so the stack holds indexes and the distance is the difference of two indexes.
def days_to_warmer(temps): answer = [0] * len(temps) stack = [] for i, t in enumerate(temps): while stack and temps[stack[-1]] < t: j = stack.pop() answer[j] = i - j stack.append(i) return answerExample 4 · Days until a warmer day
def days_to_warmer(temps): answer = [0] * len(temps) stack = [] for i, t in enumerate(temps): while stack and temps[stack[-1]] < t: j = stack.pop() answer[j] = i - j stack.append(i) return answer
print(days_to_warmer([73, 74, 75, 71, 69, 72, 76, 73]))[1, 1, 4, 2, 1, 1, 0, 0]
What this code does
- Day 0 is 73 and day 1 is 74, so day 0 waits 1 day.
- The last day never finds a warmer one, so its answer stays 0.
Example 5 · Stock span
def spans(prices): result = [] stack = [] for i, price in enumerate(prices): while stack and prices[stack[-1]] <= price: stack.pop() result.append(i - stack[-1] if stack else i + 1) stack.append(i) return result
print(spans([100, 80, 60, 70, 60, 75, 85]))[1, 1, 1, 2, 1, 4, 6]
What this code does
- The span is how many days in a row, ending today, had a price at most today's price.
- Popping smaller or equal prices leaves the nearest higher price on top. The distance to it is the span.
A day that never finds a warmer day stays at 0.
Largest rectangle in a histogram
Bars have heights and width 1. A rectangle uses a run of bars and is as tall as the shortest bar in it. Keep a stack of bars with rising heights. A lower bar ends the taller ones, and each ended bar gives one rectangle.
def largest_rectangle(heights): best = 0 stack = [] for i, h in enumerate(heights + [0]): start = i while stack and stack[-1][1] >= h: start, height = stack.pop() best = max(best, height * (i - start)) stack.append((start, h)) return bestExample 6 · Brute force histogram
def largest_rectangle_slow(heights): best = 0 for i in range(len(heights)): low = heights[i] for j in range(i, len(heights)): low = min(low, heights[j]) best = max(best, low * (j - i + 1)) return best
print(largest_rectangle_slow([2, 1, 5, 6, 2, 3]))10
What this code does
- Try every start
iand extend to the right while tracking the lowest bar. The time is O(n squared) with O(1) space. - The best rectangle uses the bars 5 and 6. Its height is 5 and its width is 2, so the area is 10.
Example 7 · Largest rectangle with a stack
def largest_rectangle(heights): best = 0 stack = [] for i, h in enumerate(heights + [0]): start = i while stack and stack[-1][1] >= h: start, height = stack.pop() best = max(best, height * (i - start)) stack.append((start, h)) return best
print(largest_rectangle([2, 1, 5, 6, 2, 3]))print(largest_rectangle([4, 4, 4]))print(largest_rectangle([7]))10 12 7
What this code does
- Heights 5 and 6 rise, then the 2 pops 6 (area 6) and 5 (area 10). The popped bars' start moves left to the 5's start.
- Equal bars are merged because of
>=. The time is O(n) and the space is O(n).
The extra 0 at the end pops every bar left on the stack. The stack stores (start, height): the popped bar's rectangle starts at start, and a new bar inherits the earliest start it can reach.
Next step
Check your understanding
11 quick questions