Greedy & Monotonic Stack — Master Recap & Cheatsheet

Greedy & Monotonic Stack Master Cheatsheet

Greedy Patterns

Pattern	Key Insight	Sort/Order
Interval Scheduling	Keep earliest-ending	Sort by end time
Interval Piercing	Same as above	Sort by end time
Candy Two-Pass	Left then right constraints	Two O(n) passes
Gas Station	If total ok, reset at negative	Linear scan
Partition Labels	Extend to last occurrence	Track last occurrence
Queue Reconstruction	Insert taller first	Sort by height desc
Assign Tasks Greedy	Match smallest sufficient	Sort both

Monotonic Stack Patterns

Pattern	Stack Type	Trigger Pop
Next Greater	Decreasing	current > stack top
Next Smaller	Increasing	current < stack top
Histogram Area	Increasing	current < stack top
Trapping Rain	Decreasing (by index)	current > stack top
Remove K Digits	Increasing	current < stack top AND k > 0
Sum Subarray Min	Increasing	current < stack top (left), right scan for right

Monotonic Stack Template

stack = []  # or [-1] for sentinel
for i, val in enumerate(arr):
    # For DECREASING stack (Next Greater Element):
    while stack and arr[stack[-1]] < val:
        idx = stack.pop()
        result[idx] = val  # val is NGE for idx
    stack.append(i)

Histogram Template

heights.append(0)  # sentinel
stack = [-1]
for i, h in enumerate(heights):
    while stack[-1] != -1 and heights[stack[-1]] >= h:
        height = heights[stack.pop()]
        width = i - stack[-1] - 1
        max_area = max(max_area, height * width)
    stack.append(i)

Problem Index

Greedy: Assign Cookies (01), Non-overlap Intervals (02), Arrows (03), Gas Station (04), Candy (05), Partition Labels (18), Queue Reconstruction (19), Min Cost Sticks (17), Max Chunks (21)

Monotonic Stack: NGE I (06), Daily Temps (07), Largest Rect Histogram (08), Trapping Rain (09), Remove Duplicates (10), Remove K Digits (11), Sum Subarray Min (12), Max Width Ramp (13), 132 Pattern (14), Maximal Rectangle (15), NGE II Circular (16)

Monotonic Deque: Jump Game VI (20)