The monotonic increasing stack is the mirror image of the decreasing stack, but it unlocks a completely different class of problems. While decreasing stacks find "next greater" elements, increasing stacks find "next smaller" elements—and this is the key to solving histogram and rectangle problems.
The most famous application? Largest Rectangle in Histogram (LeetCode #84), one of the most elegant O(n) algorithms you'll ever encounter. It seems impossible at first: how can you find the largest rectangle in linear time?
This comprehensive guide will teach you the complete increasing stack template, why it finds next smaller elements, how it solves histogram problems, and the common mistakes that lead to wrong answers.
Use monotonic increasing stack when:
Template:
stack = [] # Store indices
for i in range(n):
while stack and nums[i] < nums[stack[-1]]:
idx = stack.pop()
# nums[i] is the next smaller for nums[idx]
stack.append(i)Time: O(n), Space: O(n)
A monotonic increasing stack maintains elements in increasing order from bottom to top.
Visual:
Bottom → Top
[1, 3, 5, 9] ✓ Increasing
[9, 5, 3, 1] ✗ Decreasing
[1, 3, 3, 5] ✓ Non-strictly increasingBefore pushing a new element, we pop all elements from the top that are greater than or equal to the new element.
This maintains the increasing property.
Array: [3, 1, 4, 1, 5, 9, 2]
Step 1: Process 3
Stack: [3]
Step 2: Process 1
1 < 3, pop 3
Stack: [1]
Step 3: Process 4
4 > 1, just push
Stack: [1, 4] (increasing ✓)
Step 4: Process 1
1 < 4, pop 4
1 = 1, pop 1
Stack: [1]
Step 5: Process 5
5 > 1, just push
Stack: [1, 5] (increasing ✓)
Step 6: Process 9
9 > 5, just push
Stack: [1, 5, 9] (increasing ✓)
Step 7: Process 2
2 < 9, pop 9
2 < 5, pop 5
2 > 1, just push
Stack: [1, 2] (increasing ✓)When you encounter an element smaller than the stack top, you've found the next smaller element for all larger elements in the stack.
Visual proof:
Array: [4, 2, 1, 5, 3]
[0 1 2 3 4] ← indices
i=0, val=4: stack=[0]
i=1, val=2:
- 2 < 4, so 2 is next smaller for index 0
- stack=[1]
i=2, val=1:
- 1 < 2, so 1 is next smaller for index 1
- stack=[2]
i=3, val=5:
- 5 > 1, just push
- stack=[2,3] (increasing)
i=4, val=3:
- 3 < 5, so 3 is next smaller for index 3
- stack=[2,4]
Result:
result[0] = 2 (next smaller for 4)
result[1] = 1 (next smaller for 2)
result[3] = 3 (next smaller for 5)Comparison:
| Pattern | Order | Finds | Comparison |
|---|---|---|---|
| Decreasing Stack | Large → Small | Next Greater | nums[i] > stack[-1] |
| Increasing Stack | Small → Large | Next Smaller | nums[i] < stack[-1] |
Mnemonic: The stack order is the opposite of what you're finding.
def next_smaller_element(nums):
"""
Find next smaller element for each position.
Args:
nums: List of integers
Returns:
List where result[i] = next smaller element for nums[i],
or -1 if no smaller element exists
Time: O(n) - each element pushed and popped at most once
Space: O(n) - stack storage
"""
n = len(nums)
result = [-1] * n # Default: no smaller element
stack = [] # Store indices (not values)
for i in range(n):
# Pop all elements greater than current
# These elements have found their next smaller (nums[i])
while stack and nums[i] < nums[stack[-1]]:
idx = stack.pop()
result[idx] = nums[i]
# Push current index
stack.append(i)
# Elements remaining in stack have no next smaller
# (already initialized to -1)
return result
# Example usage
print(next_smaller_element([4, 2, 1, 5, 3]))
# Output: [2, 1, -1, 3, -1]
# Explanation:
# - Next smaller for 4 is 2
# - Next smaller for 2 is 1
# - No next smaller for 1
# - Next smaller for 5 is 3
# - No next smaller for 3function nextSmallerElement(nums) {
const n = nums.length;
const result = new Array(n).fill(-1);
const stack = [];
for (let i = 0; i < n; i++) {
// Pop elements greater than current
while (stack.length > 0 && nums[i] < nums[stack[stack.length - 1]]) {
const idx = stack.pop();
result[idx] = nums[i];
}
stack.push(i);
}
return result;
}
// Example
console.log(nextSmallerElement([4, 2, 1, 5, 3]));
// Output: [2, 1, -1, 3, -1]public int[] nextSmallerElement(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
// Pop elements greater than current
while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
int idx = stack.pop();
result[idx] = nums[i];
}
stack.push(i);
}
return result;
}This is the canonical monotonic increasing stack problem and one of the most beautiful algorithms in computer science.
Given an array of integers representing histogram bar heights, find the area of the largest rectangle in the histogram.
For each bar, the largest rectangle with that bar as the height is determined by:
Visual:
Heights: [2, 1, 5, 6, 2, 3]
[0 1 2 3 4 5]
For bar at index 2 (height 5):
- Next smaller to left: index 1 (height 1)
- Next smaller to right: index 4 (height 2)
- Width: 4 - 1 - 1 = 2
- Area: 5 × 2 = 10def largestRectangleArea(heights):
"""
LeetCode #84: Largest Rectangle in Histogram
Approach: Monotonic increasing stack
- For each bar, find next smaller on both sides
- Calculate area with current bar as height
Time: O(n)
Space: O(n)
"""
# Add sentinel values to handle edge cases
heights = [0] + heights + [0]
stack = [] # Store indices, maintain increasing heights
max_area = 0
for i in range(len(heights)):
# When we find a shorter bar, calculate areas
while stack and heights[i] < heights[stack[-1]]:
h_idx = stack.pop()
height = heights[h_idx]
# Width: distance between next smaller elements
# Left boundary: stack[-1] (next smaller to left)
# Right boundary: i (next smaller to right)
width = i - stack[-1] - 1
area = height * width
max_area = max(max_area, area)
stack.append(i)
return max_area
# Example
print(largestRectangleArea([2, 1, 5, 6, 2, 3]))
# Output: 10
# Explanation: Rectangle with height 5, width 2 (bars at indices 2 and 3)Adding [0] at the beginning and end:
Without sentinels, you'd need extra logic to handle edge cases.
Heights: [0, 2, 1, 5, 6, 2, 3, 0] (with sentinels)
[0 1 2 3 4 5 6 7]
i=0, h=0: stack=[0]
i=1, h=2: 2 > 0, stack=[0,1]
i=2, h=1:
- 1 < 2, pop 1, height=2, width=2-0-1=1, area=2×1=2
- 1 > 0, stack=[0,2]
i=3, h=5: 5 > 1, stack=[0,2,3]
i=4, h=6: 6 > 5, stack=[0,2,3,4]
i=5, h=2:
- 2 < 6, pop 4, height=6, width=5-3-1=1, area=6×1=6
- 2 < 5, pop 3, height=5, width=5-2-1=2, area=5×2=10 ← MAX
- 2 > 1, stack=[0,2,5]
i=6, h=3: 3 > 2, stack=[0,2,5,6]
i=7, h=0:
- 0 < 3, pop 6, height=3, width=7-5-1=1, area=3×1=3
- 0 < 2, pop 5, height=2, width=7-2-1=4, area=2×4=8
- 0 < 1, pop 2, height=1, width=7-0-1=6, area=1×6=6
- stack=[0]
Maximum area: 10See detailed guide: Histogram Mistakes
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's.
Reduce 2D to 1D: Treat each row as the base of a histogram, where the height is the number of consecutive 1's above (including current row).
Visual:
Matrix:
[1, 0, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 1, 1, 1]
[1, 0, 0, 1, 0]
Histograms for each row:
Row 0: [1, 0, 1, 0, 0]
Row 1: [2, 0, 2, 1, 1]
Row 2: [3, 1, 3, 2, 2]
Row 3: [4, 0, 0, 3, 0]
Apply largest rectangle algorithm to each histogram.def maximalRectangle(matrix):
"""
LeetCode #85: Maximal Rectangle
Approach: Convert each row to histogram, apply largest rectangle
Time: O(rows × cols)
Space: O(cols)
"""
if not matrix or not matrix[0]:
return 0
cols = len(matrix[0])
heights = [0] * cols
max_area = 0
for row in matrix:
# Update histogram heights
for i in range(cols):
if row[i] == '1':
heights[i] += 1
else:
heights[i] = 0
# Find largest rectangle in current histogram
max_area = max(max_area, largestRectangleArea(heights))
return max_area
# Example
matrix = [
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
print(maximalRectangle(matrix))
# Output: 6
# Explanation: Rectangle from (1,2) to (2,4) has area 2×3=6To find the previous smaller element (to the left), we can use the stack differently:
def previous_smaller_element(nums):
"""
Find previous smaller element for each position.
Stack top is always the previous smaller.
Time: O(n)
Space: O(n)
"""
n = len(nums)
result = [-1] * n
stack = [] # Maintain increasing order
for i in range(n):
# Pop elements >= current
while stack and nums[i] <= nums[stack[-1]]:
stack.pop()
# Stack top is previous smaller (if exists)
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
# Example
print(previous_smaller_element([4, 2, 1, 5, 3]))
# Output: [-1, -1, -1, 1, 1]
# Explanation:
# - 4: no previous smaller
# - 2: no previous smaller
# - 1: no previous smaller
# - 5: previous smaller is 1
# - 3: previous smaller is 1For histogram problems, we need next smaller on both sides:
def find_next_smaller_boundaries(nums):
"""
Find next smaller element on both left and right.
Returns (left_boundaries, right_boundaries)
Time: O(n)
Space: O(n)
"""
n = len(nums)
left = [-1] * n # Next smaller to left
right = [n] * n # Next smaller to right
stack = []
# Find next smaller to right
for i in range(n):
while stack and nums[i] < nums[stack[-1]]:
idx = stack.pop()
right[idx] = i
stack.append(i)
# Find next smaller to left
stack = []
for i in range(n - 1, -1, -1):
while stack and nums[i] < nums[stack[-1]]:
idx = stack.pop()
left[idx] = i
stack.append(i)
return left, right
# Example
nums = [2, 1, 5, 6, 2, 3]
left, right = find_next_smaller_boundaries(nums)
print(f"Left: {left}") # [-1, -1, 1, 2, 1, 4]
print(f"Right: {right}") # [1, 6, 4, 4, 6, 6]Finding next smaller element
Histogram or rectangle problems
Finding previous smaller element
Range queries with minimum
Finding next greater element
Sliding window problems
Need all elements, not just boundaries
❌ Wrong:
# Want next SMALLER, but using > instead of <
while stack and nums[i] > nums[stack[-1]]: # WRONG
stack.pop()✅ Correct:
# Next SMALLER needs < comparison
while stack and nums[i] < nums[stack[-1]]: # CORRECT
idx = stack.pop()
result[idx] = nums[i]❌ Wrong:
width = i - stack[-1] # Off by one!✅ Correct:
width = i - stack[-1] - 1 # Correct
# Explanation: Exclude both boundariesWhy -1? The boundaries (at stack[-1] and i) are the next smaller elements, so they're not included in the rectangle.
❌ Wrong:
for i in range(n):
while stack and nums[i] < nums[stack[-1]]:
# Process...
stack.append(i)
# Stack may still have elements!✅ Correct:
# Add sentinel at end to force processing
nums = nums + [0] # Or handle remaining stack separately❌ Wrong:
# Without sentinels, need complex edge case handling
for i in range(len(heights)):
# ...
if stack: # Check if empty
width = i - stack[-1] - 1
else:
width = i # Special case✅ Correct:
# With sentinels, no special cases needed
heights = [0] + heights + [0]
# Stack is never empty, all bars processedSee guide: Histogram Mistakes
heights = [3, 3, 3, 3]
# Largest rectangle: 3 × 4 = 12heights = [1, 2, 3, 4, 5]
# Each bar's rectangle is limited by its own height
# Largest: 3 × 3 = 9 (middle bar)heights = [5, 4, 3, 2, 1]
# Widest rectangle: 1 × 5 = 5heights = [5]
# Largest rectangle: 5 × 1 = 5Amortized analysis:
For histogram: O(n) for single pass, even with while loop inside for loop.
Worst case: All elements in increasing order
See detailed proof: Why Stack Beats Brute Force
Master the increasing stack with these problems:
Beginner:
Intermediate:
4. Largest Rectangle in Histogram (#84) ⭐⭐ - Canonical problem
5. Maximal Rectangle (#85) - 2D extension
6. Sum of Subarray Minimums (#907) - Contribution technique
Advanced:
7. Maximum Width Ramp (#962) - Variant
8. Sum of Subarray Ranges (#2104) - Bidirectional
9. Minimum Cost Tree From Leaf Values (#1130) - DP + stack
Q: Why increasing order for next smaller?
A: When we find a smaller element, we know it's the next smaller for all larger elements in the stack. Increasing order ensures we process them correctly.
Q: How do I remember which direction?
A: Mnemonic: The stack order is the opposite of what you're finding.
Q: Why are sentinels useful in histogram?
A: Sentinels (0 at both ends) eliminate edge cases:
Q: Can I use this for 2D problems?
A: Yes! Maximal Rectangle converts each row to a 1D histogram, then applies the increasing stack algorithm.
The monotonic increasing stack is a powerful pattern for finding next smaller elements and solving histogram problems in O(n) time.
Key principles:
The template:
stack = []
for i in range(n):
while stack and nums[i] < nums[stack[-1]]:
result[stack.pop()] = nums[i]
stack.append(i)When to use:
Master this template, and you'll solve some of the most elegant problems in computer science. For the opposite pattern, see Monotonic Decreasing Stack Template. For the complete overview, see Monotonic Stack & Queue Guide.
Next time you see "histogram" or "largest rectangle," reach for the increasing stack.
LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free