A monotonic stack is a powerful data structure and algorithm pattern that maintains elements in either strictly increasing or decreasing order. It’s particularly useful for solving array-based problems that involve finding the next greater or smaller element, calculating spans, or identifying boundaries efficiently. Unlike brute-force approaches that might require O(n²) time complexity, monotonic stacks often solve these problems in just O(n) time, making them perfect for technical interviews.
In this post, I’ll guide you through six classic LeetCode problems that leverage the monotonic stack pattern, from straightforward applications to more complex scenarios.
Problem:
Given an array of integers temperatures representing daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] = 0.
Example:
Python Solution:
class Solution:
def dailyTemperatures(self, nums: List[int]) -> List[int]:
stack = []
ans = [0] * len(nums)
for cur_day, cur_temp in enumerate(nums):
while stack and cur_temp > stack[-1][1]:
past_day, past_temp = stack.pop()
ans[past_day] = cur_day - past_day
stack.append((cur_day, cur_temp))
return ans
Explanation:
This is a classic application of a monotonic decreasing stack. We store pairs of (day_index, temperature) in our stack. For each current temperature:
Time Complexity: O(n) — Each element is pushed and popped at most once.
Space Complexity: O(n) — In the worst case, the stack stores all temperatures.
Edge Cases:
Problem:
Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums), return the next greater number for every element in nums. The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.
Example:
Python Solution:
class Solution:
def nextGreaterElements(self, nums):
n = len(nums)
nums = nums + nums # Duplicate array to handle circular nature
out = [-1] * n
stack = []
for index, val in enumerate(nums):
while stack and stack[-1][1] < val:
out[(stack[-1][0]) % n] = val
stack.pop()
stack.append((index, val))
return out
Explanation:
This problem extends the classic “next greater element” problem by adding the circular array constraint. The elegant approach here:
Time Complexity: O(n) — Each element is processed at most twice.
Space Complexity: O(n) — Stack size and duplicated array.
Edge Cases:
Problem:
Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
Example:
Python Solution:
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
"""
Algorithm:
- push -1 on the stack
- keep pushing on the stack if the cur height is greater than one on the top of the stack
- keep only indexes in the stack
- while popping any height
- the max rectangle with that height is
- first height < cur on the left and on the right.
- i.e. cur - stack top - 1 * cur_height
- add additional zero towards the end to make popping easy
"""
heights.append(0) # Add sentinel to ensure all bars are processed
stack = [-1] # Initialize with -1 to handle edge cases
ans = 0
for index in range(len(heights)):
while stack[-1] != -1 and heights[stack[-1]] > heights[index]:
ans_index = stack.pop()
left, right = stack[-1], index
ans = max(ans, (right - left - 1) * heights[ans_index])
stack.append(index)
return ans
Explanation:
This is a more complex application of monotonic stacks. The key insight:
Time Complexity: O(n) — Each bar is pushed and popped exactly once.
Space Complexity: O(n) — Stack size in worst case.
Edge Cases:
Problem:
There are n people standing in a queue, numbered from 0 to n-1 in left to right order. You are given an array heights of distinct integers where heights[i] represents the height of the ith person. A person can see another person to their right in the queue if everybody in between is shorter than both of them. More formally, the ith person can see the jth person if i < j and min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]). Return an array answer where answer[i] is the number of people the ith person can see to their right in the queue.
Example:
Python Solution:
class Solution:
def canSeePersonsCount(self, heights: List[int]) -> List[int]:
stack = []
ans = []
n = len(heights)
for x in range(n-1, -1, -1):
ret = 0
while stack and heights[x] >= stack[-1]:
stack.pop()
ret += 1
ans.append(ret + (1 if stack else 0))
stack.append(heights[x])
return ans[::-1]
Explanation:
This solution uses a monotonic stack to track visible people, processing from right to left:
Time Complexity: O(n) — Each height is pushed and popped at most once.
Space Complexity: O(n) — Stack size in worst case.
Edge Cases:
Problem:
Given an array of unique integers preorder, return true if it is the correct preorder traversal sequence of a binary search tree.
Example:
Python Solution:
class Solution:
def verifyPreorder(self, preorder: List[int]) -> bool:
stack = []
min_val = float("-inf")
for val in preorder:
while stack and stack[-1] < val:
min_val = max(min_val, stack.pop())
if val <= min_val:
return False
stack.append(val)
return True
Explanation:
This problem combines BST properties with monotonic stacks. The key insight:
Time Complexity: O(n) — Each element is processed exactly once.
Space Complexity: O(n) — Stack size in worst case.
Edge Cases:
Problem:
Given string num representing a non-negative integer, and an integer k, return the smallest possible integer after removing k digits from num.
Example:
Python Solution:
class Solution:
def removeKdigits(self, num, k):
st = []
for n in num:
while st and st[-1] > n and k:
st.pop()
k -= 1
if st or n != '0':
st.append(n)
if k:
st = st[0:-k]
return ''.join(st) or '0'
Explanation:
This problem is a perfect application of a monotonic increasing stack:
Time Complexity: O(n) — Each digit is processed at most twice.
Space Complexity: O(n) — Stack size in worst case.
Edge Cases:
Pattern Recognition:
Stack Type Selection:
Implementation Efficiency:
Circular Array Handling:
Greedy Decision Making:
Happy coding, and good luck with your next interview!
Follow me for more algorithm insights and Python solutions!