API Kernel:
MonotonicStackCore Mechanism: Boundary / Candidate Resolution via Monotonicity — maintain a stack in strictly or non-strictly increasing/decreasing order to efficiently resolve boundary queries (next greater, next smaller, span, interval expansion) in amortized O(1) per element.
This document presents the canonical monotonic stack template and all its major variations. Each implementation follows consistent naming conventions and includes detailed algorithmic explanations.
- Core Concepts
- Base Template: Next Greater / Next Smaller Boundaries
- Variation: Circular Boundary Search
- Variation: Histogram / Interval Expansion
- Variation: Span / Distance Aggregation
- Variation: Contribution / Counting via Boundaries
- Variation: Container / Valley Resolution
- Variation: Greedy Monotonic Stack
- Off-by-One, Comparison Semantics, and Robustness
- Termination Guarantees (Amortized Analysis)
- Pattern Comparison Table
- When to Use Monotonic Stack
- LeetCode Problem Mapping
- Template Quick Reference
A monotonic stack is a stack that maintains elements in a monotonically increasing or decreasing order. When a new element violates this order, we pop elements from the stack until the invariant is restored.
Monotonic Decreasing Stack (for Next Greater Element):
┌─────────────────────────────────────────────────────────────┐
│ Push: Only push if element < stack top (maintains order) │
│ Pop: Pop while stack top < current element │
│ → Each popped element finds its "next greater" │
│ │
│ Stack state: [largest, ..., smallest] │
│ └──── bottom ────┘ └─ top │
└─────────────────────────────────────────────────────────────┘
The monotonic stack solves a fundamental class of problems: finding the nearest element satisfying a comparison condition. This includes:
- Next Greater Element (NGE): For each element, find the first element to the right that is greater
- Previous Smaller Element (PSE): For each element, find the first element to the left that is smaller
- Span queries: How many consecutive elements are smaller/greater?
- Interval expansion: How far can we extend left/right while maintaining a property?
All these reduce to the same core mechanism: when we pop an element from the stack, the current element becomes its boundary.
Every monotonic stack algorithm maintains this invariant:
Invariant: The stack contains candidate elements that have not yet found their boundary, ordered monotonically.
When we encounter a new element that violates the monotonic order:
- Pop elements until order is restored
- Each popped element has found its boundary (the current element)
- Push the current element as a new candidate
Always store indices in the stack, not values. This provides:
- Access to both position and value via
arr[stack[-1]] - Ability to compute distances (
current_index - stack[-1]) - Consistent interface across all monotonic stack variants
# Canonical: Store indices
stack = [] # stack of indices
for i, val in enumerate(arr):
while stack and arr[stack[-1]] < val:
idx = stack.pop()
# arr[idx] found its next greater at position i
stack.append(i) # Push index, not valueThe key insight of monotonic stack is that boundaries are resolved when elements are popped, not when they are pushed:
Processing: [2, 1, 5, 6, 2, 3]
Step 1: Push 2 (idx=0) Stack: [0]
Step 2: Push 1 (idx=1) Stack: [0, 1] (1 < 2, order maintained)
Step 3: See 5
Pop 1 → 1's NGE is 5 (at idx=2)
Pop 2 → 2's NGE is 5 (at idx=2)
Push 5 (idx=2) Stack: [2]
Step 4: Push 6 (idx=3) Stack: [2, 3]
Step 5: See 2
(2 < 6, just push)
Push 2 (idx=4) Stack: [2, 3, 4]
Step 6: See 3
Pop 2 → 2's NGE is 3 (at idx=5)
Push 3 (idx=5) Stack: [2, 3, 5]
Final: Elements [5, 6, 3] have no NGE (remain in stack)
| Sub-Pattern | Key Characteristic | Examples |
|---|---|---|
| Next Greater/Smaller | Find boundary element | LeetCode 496, 739 |
| Circular Boundary | 2n traversal for wrap-around | LeetCode 503 |
| Histogram Expansion | Left/right smaller for area | LeetCode 84, 85 |
| Span/Distance | Count consecutive dominated elements | LeetCode 901 |
| Contribution Counting | Sum via boundary products | LeetCode 907, 2104 |
| Container/Valley | Water trapped between walls | LeetCode 42 |
| Greedy Monotonic | Optimal prefix selection | LeetCode 402 |
Pattern: Find, for each element, the nearest element satisfying a comparison condition. Invariant: Stack contains indices of elements awaiting their boundary, in monotonic order. Role: BASE TEMPLATE for
MonotonicStackAPI Kernel.
| Pattern | Direction | Stack Order | Comparison | Common Name |
|---|---|---|---|---|
| NGE-R | Next Greater to Right | Decreasing | > |
Next Greater Element |
| NGE-L | Next Greater to Left | Decreasing (reverse) | > |
Previous Greater Element |
| NSE-R | Next Smaller to Right | Increasing | < |
Next Smaller Element |
| PSE-L | Previous Smaller to Left | Increasing (reverse) | < |
Previous Smaller Element |
def next_greater_element(nums: list[int]) -> list[int]:
"""
For each element, find the next greater element to its right.
Returns -1 if no such element exists.
Algorithm:
- Maintain a monotonically decreasing stack (by value)
- When current element > stack top, stack top found its NGE
- Each element is pushed once and popped at most once → O(n)
Time: O(n), Space: O(n)
"""
n = len(nums)
result = [-1] * n # Default: no next greater
stack = [] # Stack of indices, values are decreasing
for i in range(n):
# Pop all elements smaller than current (they found their NGE)
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i] # or result[idx] = i for index
stack.append(i)
return resultdef previous_smaller_element(nums: list[int]) -> list[int]:
"""
For each element, find the previous smaller element to its left.
Returns -1 if no such element exists.
Algorithm:
- Maintain a monotonically increasing stack (by value)
- For each element, pop until we find a smaller element
- The stack top (if exists) is the previous smaller element
Time: O(n), Space: O(n)
"""
n = len(nums)
result = [-1] * n
stack = [] # Stack of indices, values are increasing
for i in range(n):
# Pop elements >= current (they can't be PSE for future elements)
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
# Stack top (if exists) is the previous smaller element
if stack:
result[i] = nums[stack[-1]] # or stack[-1] for index
stack.append(i)
return resultThe same algorithm can return different information based on the problem:
def next_greater_variants(nums: list[int]) -> tuple[list[int], list[int], list[int]]:
"""
Compute NGE returning value, index, and distance.
"""
n = len(nums)
nge_value = [-1] * n # The value of next greater element
nge_index = [-1] * n # The index of next greater element
nge_distance = [0] * n # Distance to next greater element
stack = []
for i in range(n):
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
nge_value[idx] = nums[i]
nge_index[idx] = i
nge_distance[idx] = i - idx
stack.append(i)
return nge_value, nge_index, nge_distanceStrict comparison (< or >): Equal elements do NOT satisfy the boundary condition.
# Strict: Find next STRICTLY greater (not equal)
while stack and nums[stack[-1]] < nums[i]: # < means strictly less
# ...Non-strict comparison (<= or >=): Equal elements DO satisfy the boundary condition.
# Non-strict: Find next greater or equal
while stack and nums[stack[-1]] <= nums[i]: # <= includes equal
# ...When to use which:
- Strict: Default for most problems (Next Greater Element)
- Non-strict: When duplicates should be treated as boundaries (e.g., contribution counting to avoid double-counting)
Problem: Find next greater element in a circular array (LeetCode 503). Key Insight: Traverse the array twice (2n iterations), but only push indices during the first pass.
def next_greater_circular(nums: list[int]) -> list[int]:
"""
Find next greater element in circular array.
Algorithm:
- Traverse array twice (indices 0 to 2n-1)
- Use modulo to wrap around: actual_index = i % n
- Only push indices during first pass (i < n)
- Second pass only resolves remaining elements
Time: O(n), Space: O(n)
"""
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
actual_idx = i % n
# Pop elements that found their circular NGE
while stack and nums[stack[-1]] < nums[actual_idx]:
idx = stack.pop()
result[idx] = nums[actual_idx]
# Only push during first pass to avoid duplicate processing
if i < n:
stack.append(actual_idx)
return resultIf we push in both passes, indices would be duplicated:
- First pass pushes index 0
- Second pass would push index 0 again (since 2n % n = 0)
By limiting pushes to the first pass, each index is pushed exactly once.
After 2n iterations:
- Elements remaining in stack have no next greater element in the circular array
- Their result stays -1 (the default)
- Single element: Result is [-1] (no other element to compare)
- All equal elements: All results are -1 (no strictly greater element)
- Strictly increasing then wraps: Each element finds its boundary in second pass
Problem: Find the largest rectangle in a histogram (LeetCode 84). Key Insight: For each bar, find its left and right boundaries (first smaller bar), then compute area.
For each bar at index i with height h:
- Left boundary: First bar to the left that is shorter (
left_smaller[i]) - Right boundary: First bar to the right that is shorter (
right_smaller[i]) - Width:
right_smaller[i] - left_smaller[i] - 1 - Area:
h * width
Histogram: [2, 1, 5, 6, 2, 3]
Bar at index 2 (height 5):
Left boundary: index 1 (height 1 < 5)
Right boundary: index 4 (height 2 < 5)
Width: 4 - 1 - 1 = 2
Area: 5 * 2 = 10
def largest_rectangle_two_pass(heights: list[int]) -> int:
"""
Largest rectangle using two passes for left/right boundaries.
Time: O(n), Space: O(n)
"""
n = len(heights)
left_smaller = [-1] * n # Index of first smaller bar to left
right_smaller = [n] * n # Index of first smaller bar to right
# Pass 1: Find left boundaries (previous smaller)
stack = []
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
left_smaller[i] = stack[-1] if stack else -1
stack.append(i)
# Pass 2: Find right boundaries (next smaller)
stack = []
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
right_smaller[i] = stack[-1] if stack else n
stack.append(i)
# Compute maximum area
max_area = 0
for i in range(n):
width = right_smaller[i] - left_smaller[i] - 1
area = heights[i] * width
max_area = max(max_area, area)
return max_areadef largest_rectangle_single_pass(heights: list[int]) -> int:
"""
Largest rectangle using single pass with sentinel.
The sentinel (0 at end) forces all remaining bars to be popped,
completing their rectangle computation.
Time: O(n), Space: O(n)
"""
heights = heights + [0] # Sentinel: forces final flush
stack = [-1] # Virtual left boundary
max_area = 0
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)
return max_areaThe sentinel pattern ensures all elements are processed:
- Right sentinel (
heights.append(0)): A bar of height 0 is smaller than all bars, forcing all stack elements to pop - Left sentinel (
stack = [-1]): A virtual boundary at index -1 handles the case when stack becomes empty
For duplicate heights, use non-strict comparison (>= instead of >):
# With duplicates: [2, 2, 2]
# Using > (strict): Each bar stops at its immediate neighbor
# Using >= (non-strict): Each bar extends through equal-height bars
while stack[-1] != -1 and heights[stack[-1]] >= h: # >= for duplicatesThis ensures correct width calculation when adjacent bars have equal height.
def maximal_rectangle(matrix: list[list[str]]) -> int:
"""
Find largest rectangle of 1s in binary matrix.
Algorithm:
- Build histogram row by row
- Each cell's height = consecutive 1s above (including current)
- Apply largest_rectangle_in_histogram to each row
Time: O(m * n), Space: O(n)
"""
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
max_area = 0
for row in matrix:
# Update histogram
for j in range(n):
heights[j] = heights[j] + 1 if row[j] == '1' else 0
# Find largest rectangle in current histogram
max_area = max(max_area, largest_rectangle_single_pass(heights[:]))
return max_areaProblem: Compute how many consecutive days the stock price was less than or equal to today's price (LeetCode 901). Key Insight: Span = distance to previous greater element.
def daily_temperatures(temperatures: list[int]) -> list[int]:
"""
For each day, find how many days until a warmer temperature.
This is the distance to the next greater element.
Time: O(n), Space: O(n)
"""
n = len(temperatures)
result = [0] * n
stack = [] # Stack of indices, temperatures are decreasing
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
idx = stack.pop()
result[idx] = i - idx # Distance to next greater
stack.append(i)
return resultclass StockSpanner:
"""
Online computation of stock span.
Span = number of consecutive days with price <= today's price.
Key insight: Span includes the current day plus all days
that were "dominated" by previous greater prices.
Stack stores (price, span) pairs.
"""
def __init__(self):
self.stack = []
def next(self, price: int) -> int:
span = 1 # Current day counts
# Pop and accumulate spans of dominated days
while self.stack and self.stack[-1][0] <= price:
_, prev_span = self.stack.pop()
span += prev_span
self.stack.append((price, span))
return spanThe span at position i represents:
- Count interpretation: Number of consecutive elements to the left that are dominated
- Distance interpretation:
i - index_of_previous_greater_element
| Aspect | Base NGE | Span/Distance |
|---|---|---|
| Resolves | Value of boundary | Distance to boundary |
| Returns | Boundary element | Count or distance |
| Stack stores | Just indices | May store (value, span) pairs |
Problem: Sum of subarray minimums (LeetCode 907). Key Insight: Each element's contribution = element × (left_count) × (right_count).
For element at index i with value v:
- Let
L= number of consecutive elements to the left wherevis the minimum - Let
R= number of consecutive elements to the right wherevis the minimum - Element's contribution to total sum =
v × L × R
This counts exactly how many subarrays have v as their minimum.
Array: [3, 1, 2, 4]
Element 1 at index 1:
L = 2 (can extend to include index 0)
R = 3 (can extend to include indices 2, 3)
Contribution = 1 × 2 × 3 = 6
Subarrays where 1 is minimum:
[3,1], [1], [1,2], [1,2,4], [3,1,2], [3,1,2,4] → 6 subarrays
def sum_of_subarray_minimums(arr: list[int]) -> int:
"""
Sum of minimums of all subarrays.
Algorithm:
- For each element, find left/right boundaries (previous/next smaller)
- Use asymmetric tie-breaking to avoid double-counting duplicates:
- Left boundary: strictly smaller (<)
- Right boundary: smaller or equal (<=)
Time: O(n), Space: O(n)
"""
MOD = 10**9 + 7
n = len(arr)
# left[i] = distance to previous smaller element
# right[i] = distance to next smaller or equal element
left = [0] * n
right = [0] * n
# Compute left boundaries (previous strictly smaller)
stack = []
for i in range(n):
while stack and arr[stack[-1]] >= arr[i]: # >= for strict <
stack.pop()
left[i] = i - stack[-1] if stack else i + 1
stack.append(i)
# Compute right boundaries (next smaller or equal)
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[stack[-1]] > arr[i]: # > for <=
stack.pop()
right[i] = stack[-1] - i if stack else n - i
stack.append(i)
# Sum contributions
result = 0
for i in range(n):
result = (result + arr[i] * left[i] * right[i]) % MOD
return resultWhen duplicates exist, we must avoid counting the same subarray twice:
- Left boundary: Use strict comparison (
<) → previous strictly smaller - Right boundary: Use non-strict comparison (
<=) → next smaller or equal
This creates a "left-closed, right-open" style where each subarray is counted exactly once.
def sum_of_subarray_ranges(nums: list[int]) -> int:
"""
Sum of (max - min) for all subarrays.
= Sum of all subarray maximums - Sum of all subarray minimums
Use dual stacks: one for max contribution, one for min contribution.
Time: O(n), Space: O(n)
"""
n = len(nums)
def sum_of_extremes(compare_greater: bool) -> int:
"""Compute sum of subarray max (if True) or min (if False)."""
left = [0] * n
right = [0] * n
stack = []
# Comparison functions for max vs min
def dominates(a, b):
return a > b if compare_greater else a < b
def dominates_or_equal(a, b):
return a >= b if compare_greater else a <= b
# Left boundaries
for i in range(n):
while stack and dominates_or_equal(nums[i], nums[stack[-1]]):
stack.pop()
left[i] = i - stack[-1] if stack else i + 1
stack.append(i)
# Right boundaries
stack = []
for i in range(n - 1, -1, -1):
while stack and dominates(nums[i], nums[stack[-1]]):
stack.pop()
right[i] = stack[-1] - i if stack else n - i
stack.append(i)
return sum(nums[i] * left[i] * right[i] for i in range(n))
sum_max = sum_of_extremes(True)
sum_min = sum_of_extremes(False)
return sum_max - sum_minProblem: Calculate trapped rainwater (LeetCode 42). Key Insight: Each "pop" completes a valley — water trapped between left wall, bottom, and right wall.
def trap(height: list[int]) -> int:
"""
Calculate total trapped rainwater.
Algorithm:
- Maintain a monotonically decreasing stack
- When we see a taller bar, we've found a valley
- Pop the bottom of the valley, compute water trapped
- Water width = current_index - left_wall_index - 1
- Water height = min(left_wall, right_wall) - bottom_height
Time: O(n), Space: O(n)
"""
stack = [] # Stack of indices, heights are decreasing
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom = stack.pop()
if not stack:
break # No left wall, water flows out
left_wall_idx = stack[-1]
left_wall_height = height[left_wall_idx]
right_wall_height = h
bottom_height = height[bottom]
width = i - left_wall_idx - 1
bounded_height = min(left_wall_height, right_wall_height) - bottom_height
water += width * bounded_height
stack.append(i)
return waterEach pop operation finalizes a container segment:
Heights: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
When we reach height 2 at index 3:
Stack before: [1, 2] (heights [1, 0])
Pop index 2 (height 0): This is the valley bottom
Left wall: index 1 (height 1)
Right wall: index 3 (height 2)
Width: 3 - 1 - 1 = 1
Bounded height: min(1, 2) - 0 = 1
Water: 1 × 1 = 1
- Bottom: The popped element (lowest point of the valley)
- Left wall: The element below the bottom in the stack
- Right wall: The current element that triggered the pop
The monotonically decreasing stack ensures:
- When we pop, the current element is taller than the popped element
- The element below the popped is also taller (or we'd have popped it earlier)
- This creates a "valley" bounded on both sides
- Empty input: Return 0
- Single element: No container possible, return 0
- Two elements: No valley possible, return 0
- No valleys (monotonic): Stack never pops with left wall, return 0
Problem: Remove K digits to get the smallest number (LeetCode 402). Key Insight: Maintain a monotonically increasing stack as the "greedy best prefix".
def remove_k_digits(num: str, k: int) -> str:
"""
Remove k digits to create the smallest possible number.
Algorithm:
- Maintain monotonically increasing stack (greedy best prefix)
- Pop larger digits when a smaller digit is seen (local optimality)
- Handle leading zeros and remaining k
Time: O(n), Space: O(n)
"""
stack = []
for digit in num:
# Pop larger digits if we can still remove (k > 0)
while k > 0 and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
# If k > 0, remove from the end (stack is increasing, end is largest)
if k > 0:
stack = stack[:-k]
# Remove leading zeros and handle empty result
result = ''.join(stack).lstrip('0')
return result if result else '0'The pop decision is locally optimal:
- If we see digit
dand stack top iss > d, removingsgives a smaller number - The monotonic increasing property ensures the "best so far" prefix
def remove_duplicate_letters(s: str) -> str:
"""
Remove duplicate letters to get lexicographically smallest result.
Each character must appear exactly once.
Additional constraints:
- Track last occurrence of each character
- Only pop if the character appears later
Time: O(n), Space: O(26) = O(1)
"""
last_occurrence = {c: i for i, c in enumerate(s)}
stack = []
in_stack = set()
for i, c in enumerate(s):
if c in in_stack:
continue
# Pop if current is smaller and popped char appears later
while stack and stack[-1] > c and last_occurrence[stack[-1]] > i:
in_stack.remove(stack.pop())
stack.append(c)
in_stack.add(c)
return ''.join(stack)| Problem | Key Constraint | Stack Order |
|---|---|---|
| 402 Remove K Digits | Remove exactly k | Increasing |
| 316 Remove Duplicate Letters | Each char once | Increasing with occurrence check |
| 321 Create Maximum Number | Combine two arrays | Decreasing (for max) |
| Comparison | Stack Order | When Elements Are Popped | Use Case |
|---|---|---|---|
< (strict) |
Decreasing | When strictly greater appears | Default NGE |
<= (non-strict) |
Decreasing | When greater or equal appears | Contribution with duplicates |
> (strict) |
Increasing | When strictly smaller appears | Default NSE |
>= (non-strict) |
Increasing | When smaller or equal appears | Histogram with duplicates |
When dealing with duplicates, use asymmetric tie-breaking:
# Left boundary: strictly smaller (exclusive)
while stack and arr[stack[-1]] >= arr[i]: # >=
# Right boundary: smaller or equal (inclusive)
while stack and arr[stack[-1]] > arr[i]: # >This creates a consistent "left-closed, right-open" convention.
Always store indices, not values:
# Canonical: Store indices
stack.append(i)
value = arr[stack[-1]]
distance = i - stack[-1]
# Anti-pattern: Store values (loses position information)
stack.append(arr[i]) # Can't compute distances!| Sentinel | Purpose | Example |
|---|---|---|
heights.append(0) |
Force flush at end | Histogram |
stack = [-1] |
Virtual left boundary | Handle empty stack |
temperatures.append(float('inf')) |
Force all elements to pop | Ensure completion |
- Empty input: Return appropriate default (0, [], etc.)
- All equal elements: Check comparison semantics
- Single element: Stack operations should handle gracefully
- Strictly increasing/decreasing: One of the boundaries may be all default
- Overflow-safe arithmetic: Use modular arithmetic for contribution counting
- No-boundary cases: Elements remaining in stack after processing
The key insight for O(n) complexity:
Total operations = pushes + pops
≤ n + n = 2n = O(n)
Each index is:
- Pushed exactly once (when we reach it)
- Popped at most once (when a boundary is found)
Therefore, the entire algorithm is O(n) despite the inner while loop.
After each iteration:
- Stack contains indices of elements without their boundary yet
- Stack is monotonically ordered (by value at those indices)
- All processed boundaries have been recorded
Each iteration either:
- Pops at least one element (progress on stack size), OR
- Pushes exactly one element and advances to next index
The while loop terminates because the stack shrinks with each pop, and there are only n elements total to pop.
| Pattern | Stack Order | Comparison | Resolves | Typical Problems |
|---|---|---|---|---|
| Next Greater (Right) | Decreasing | < |
On pop | 496, 503, 739 |
| Previous Greater (Left) | Decreasing | < |
On peek | 901 |
| Next Smaller (Right) | Increasing | > |
On pop | 84 |
| Previous Smaller (Left) | Increasing | > |
On peek | 84, 907 |
| Histogram Area | Increasing | >= |
On pop | 84, 85 |
| Contribution Counting | Both | Asymmetric | Both | 907, 2104 |
| Trapped Water | Decreasing | < |
On pop | 42 |
| Greedy Digit Removal | Increasing | > |
On pop | 402, 316 |
✅ Use monotonic stack when:
- Finding "next greater/smaller element" for each position
- Computing spans or distances to boundaries
- Calculating contributions based on interval widths
- Processing histograms or finding maximal rectangles
- Greedy digit/character selection with order constraints
❌ Don't use monotonic stack when:
- No boundary/comparison relationship between elements
- Need random access to boundaries (use precomputation)
- Problem requires bidirectional boundaries simultaneously (may need two passes)
- Simpler O(n) traversal suffices
Is there a "nearest element satisfying a condition" query?
├── Yes → Is the condition based on comparison (>, <, >=, <=)?
│ ├── Yes → Monotonic Stack
│ │ ├── Finding boundaries → Base template
│ │ ├── Computing areas/spans → Histogram pattern
│ │ ├── Counting subarrays → Contribution pattern
│ │ ├── Trapping water/valleys → Container pattern
│ │ └── Greedy selection → Greedy monotonic stack
│ └── No → Other technique (hash map, etc.)
└── No → Monotonic stack probably doesn't apply
| Problem ID | Problem Name | Sub-Pattern |
|---|---|---|
| 496 | Next Greater Element I | NGE with hash map |
| 503 | Next Greater Element II | Circular NGE |
| 739 | Daily Temperatures | NGE distance |
| 901 | Online Stock Span | Previous greater span |
| Problem ID | Problem Name | Sub-Pattern |
|---|---|---|
| 84 | Largest Rectangle in Histogram | Interval expansion |
| 85 | Maximal Rectangle | Matrix to histogram |
| Problem ID | Problem Name | Sub-Pattern |
|---|---|---|
| 907 | Sum of Subarray Minimums | Min contribution |
| 2104 | Sum of Subarray Ranges | Max - min contribution |
| Problem ID | Problem Name | Sub-Pattern |
|---|---|---|
| 42 | Trapping Rain Water | Valley resolution |
| Problem ID | Problem Name | Sub-Pattern |
|---|---|---|
| 402 | Remove K Digits | Greedy increasing |
| 316 | Remove Duplicate Letters | Greedy with constraints |
| 321 | Create Maximum Number | Dual greedy |
def next_greater(arr):
n, result, stack = len(arr), [-1] * len(arr), []
for i in range(n):
while stack and arr[stack[-1]] < arr[i]:
result[stack.pop()] = arr[i]
stack.append(i)
return resultdef prev_smaller(arr):
n, result, stack = len(arr), [-1] * len(arr), []
for i in range(n):
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
result[i] = arr[stack[-1]] if stack else -1
stack.append(i)
return resultdef largest_rectangle(heights):
heights, stack, max_area = heights + [0], [-1], 0
for i, h in enumerate(heights):
while stack[-1] != -1 and heights[stack[-1]] > h:
height = heights[stack.pop()]
max_area = max(max_area, height * (i - stack[-1] - 1))
stack.append(i)
return max_areadef trap(height):
stack, water = [], 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom = stack.pop()
if stack:
w = i - stack[-1] - 1
bounded = min(height[stack[-1]], h) - height[bottom]
water += w * bounded
stack.append(i)
return waterdef sum_subarray_mins(arr):
n, MOD = len(arr), 10**9 + 7
left, right, stack = [0]*n, [0]*n, []
for i in range(n):
while stack and arr[stack[-1]] >= arr[i]: stack.pop()
left[i] = i - stack[-1] if stack else i + 1
stack.append(i)
stack = []
for i in range(n-1, -1, -1):
while stack and arr[stack[-1]] > arr[i]: stack.pop()
right[i] = stack[-1] - i if stack else n - i
stack.append(i)
return sum(arr[i] * left[i] * right[i] for i in range(n)) % MODDocument generated for NeetCode Practice Framework — API Kernel: MonotonicStack