Introduction
Monotonic stacks are a concept that is notoriously difficult to understand. Here, we aim to showcase the underlying threads that connect these different concepts together.
The high level concept is used when we want to quickly (in `O(1)`) determine the next greater element. For example: [3,1,7,2,9]. If we want to determine the next greater element of 3, that is 7. If we construct an array for this based on indices, we get NG = [2, 2, 4, 4, 5]. Note that index 5 is outside the array, because there is no next greater element than 9.
(You may think that finding a next greater array is contrived – when would we ever need this? But in fact, the use cases are plentiful, as you will see in the problems section)
There are actually 8 cases we can look at: next greater, next greater or equal, next smaller, next smaller or equal, and those 4 versions but PREVIOUS. (so the previous index that is greater, etc.)
Thankfully, we have 1 master template that you need to remember that can solve all 8 cases.
O(n)O(n)Master Template
This template can handle all 8 cases by only changing X, Y, Z parameters.
Parameters:
- X: Either -1 (for Previous cases) or n (for Next cases)
- Y: Either range(n) (iterate forward for Next) or range(n-1, -1, -1) (iterate backwards for Previous)
- Z: Either >=, >, <=, or < depending on the case
def f(A):
n = len(A)
stack = []
res = [X] * n
for i in range(Y):
while stack and A[stack[-1]] (Z) A[i]:
res[stack[-1]] = i
stack.pop()
stack.append(i)
return resThe 8 Cases Table
Understanding the relationship between X, Y, Z parameters for all 8 cases:
Cases by Stack Type
| Direction | Mono Increasing (Z = >=) | Mono Non-Decreasing (Z = >) | Mono Decreasing (Z = <=) | Mono Non-Increasing (Z = <) |
|---|---|---|---|---|
| Previous (X = -1, Y = n-1,-1,-1) | PLE | PL | PGE | PG |
| Next (X = n, Y = n) | NLE | NL | NGE | NG |
Parameter Reference Table
| Case | X | Y | Z | Description |
|---|---|---|---|---|
| PLE | -1 | range(n-1,-1,-1) | >= | Previous Less or Equal |
| PL | -1 | range(n-1,-1,-1) | > | Previous Less |
| PGE | -1 | range(n-1,-1,-1) | <= | Previous Greater or Equal |
| PG | -1 | range(n-1,-1,-1) | < | Previous Greater |
| NLE | n | range(n) | >= | Next Less or Equal |
| NL | n | range(n) | > | Next Less |
| NGE | n | range(n) | <= | Next Greater or Equal |
| NG | n | range(n) | < | Next Greater |
Example Walkthrough
Let's walk through an example to understand how the algorithm works.
Reverse the thinking: Instead of starting from an index and finding its NLE, reverse the thinking. From an NLE index, what are the original indices?
For example: at index i = 1, what indices j have NLE[j] = i?
- j < i (j must come before i)
- A[j] >= A[i] (j's value must be >= i's value)
- There can't be any indices k where j < k < i such that A[k] <= A[j] (no closer valid index)
The Algorithm:
Maintain a list of indices j where j < i and A[j] is monotonically increasing. At index i, all values A[j] >= A[i] have NLE equal to this current index i.
Think of it like graphing the values on an x,y plane and connecting with a line. We have a downward (or upward for mono increasing) trend line. If we see another value that continues the downward trend, we add it. Otherwise, we pop from the front of the downward line until the new point continues the new downward trend.
Step-by-Step Example
Key observation: Suppose we have a decreasing sequence followed by a greater number. For example [5, 4, 3, 2, 1, 6], then the greater number 6 is the next greater element for all previous numbers in the sequence.
We use a stack to keep a decreasing sub-sequence. Whenever we see a number x greater than stack.peek(), we pop all elements less than x, and for all the popped ones, their next greater element is x.
Example: [9, 8, 7, 3, 2, 1, 6]
- The stack will first contain [9, 8, 7, 3, 2, 1]
- Then we see 6 which is greater than 1, so we pop 1, 2, 3 whose next greater element should be 6
Contribution Technique
This is an advanced technique that involves reversing your thinking. Instead of focusing on subarrays, let's focus on specific values and how much they contribute amongst all subarrays they are a part of.
This technique is particularly useful for problems that ask for the sum of minimums/maximums across all subarrays.
For each element A[i], determine:
1. How many subarrays have A[i] as their minimum/maximum?
2. Calculate: num_subarrays = (i - left[i]) * (right[i] - i)
3. Where left[i] is the previous less/greater index, and right[i] is the next less/greater index
This allows us to calculate the total contribution in O(n) time using monotonic stacks.
Problems
Practice problems for this topic.
01Next Greater Element IEasy
The next greater element of some element x in an array is the first greater element that is to the right of x in the same array. Given two distinct arrays nums1 and nums2 where nums1 is a subset of nums2, find the next greater element for each element in nums1.
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
def ng(A):
n = len(A)
stack = []
res = [n] * n
for i in range(n):
while stack and A[stack[-1]] < A[i]:
res[stack[-1]] = i
stack.pop()
stack.append(i)
return res
idx_map = {v:i for i,v in enumerate(nums2)}
NG = ng(nums2)
res = [-1] * len(nums1)
for i in range(len(nums1)):
idx = NG[idx_map[nums1[i]]]
if idx != len(nums2):
res[i] = nums2[idx]
return resO(n + m)O(n)Direct application of the next greater template with index mapping.
02Daily TemperaturesMedium
Given an array of daily temperatures, return an array where answer[i] is the number of days you have to wait for a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0.
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
stack = []
n = len(temperatures)
res = [0] * n
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
idx = stack.pop()
res[idx] = i - idx
stack.append(i)
return resO(n)O(n)The answer is the difference between the index of the next greater element and the current element.
03Online Stock SpanMedium
Design an algorithm that collects daily price quotes for some stock and returns the span of that stock's price for the current day. The span is the maximum number of consecutive days (starting from today and going backward) for which the stock price was less than or equal to today's price.
class StockSpanner:
def __init__(self):
self.stack = []
def next(self, price: int) -> int:
ans = 1
while self.stack and self.stack[-1][0] <= price:
ans += self.stack.pop()[1]
self.stack.append((price, ans))
return ansO(n) amortizedO(n)Dynamic NGE template. Store (price, span_value) pairs to save redundant work.
04Next Greater Element IIMedium
Given a circular integer array, return the next greater number for every element. If it doesn't exist, return -1.
def nextGreaterElements(self, A: List[int]) -> List[int]:
def ng(A):
n = len(A)
stack = []
res = [n] * n
for i in range(n):
while stack and A[stack[-1]] < A[i]:
res[stack[-1]] = i
stack.pop()
stack.append(i)
return res
NG = ng(A + A)
n = len(A)
res = [-1] * n
for i in range(n):
if NG[i] != 2*n:
res[i] = A[NG[i] % n]
return resO(n)O(n)Common trick for circular arrays: double up the array.
05Largest Rectangle in HistogramHard
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.
def largestRectangleArea(self, heights: List[int]) -> int:
def nl(A):
n = len(A)
stack = []
res = [n] * n
for i in range(n):
while stack and A[stack[-1]] > A[i]:
res[stack[-1]] = i
stack.pop()
stack.append(i)
return res
def pl(A):
n = len(A)
stack = []
res = [-1] * n
for i in range(n-1, -1, -1):
while stack and A[stack[-1]] > A[i]:
res[stack.pop()] = i
stack.append(i)
return res
NL = nl(heights)
PL = pl(heights)
return max(heights[i] * (NL[i] - PL[i] - 1) for i in range(len(heights)))O(n)O(n)The maximal rectangle must fully include some bar. Height is the bar, width is determined by PL and NL. Formula: max(heights[i] * (nl[i] - pl[i] - 1))
06Maximal RectangleHard
Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if not matrix or not matrix[0]:
return 0
m, n = len(matrix), len(matrix[0])
heights = [0] * n
res = 0
for i in range(m):
for j in range(n):
heights[j] = 0 if matrix[i][j] == '0' else heights[j] + 1
res = max(res, self.largestRectangleArea(heights))
return resO(m * n)O(n)Reduce 2D to 1D: compress each row into a heights array, then apply Q84. This is the power of problem reduction!
07Sum of Subarray MinimumsMedium
Given an array of integers arr, find the sum of min(b) for every contiguous subarray b. Return answer modulo 10^9 + 7.
def sumSubarrayMins(self, A: List[int]) -> int:
MOD = 10 ** 9 + 7
n = len(A)
# Next Less or Equal on the right
right = [n] * n
stack = []
for i in range(n):
while stack and A[stack[-1]] >= A[i]:
right[stack.pop()] = i
stack.append(i)
# Previous Less on the left
left = [-1] * n
stack = []
for i in range(n-1, -1, -1):
while stack and A[stack[-1]] > A[i]:
left[stack.pop()] = i
stack.append(i)
res = 0
for i in range(n):
l, r = left[i], right[i]
num_subarrays = (i - l) * (r - i)
res = (res + A[i] * num_subarrays) % MOD
return resO(n)O(n)Contribution technique: for each A[i], count subarrays where A[i] is minimum. Use PL + NLE (or PLE + NL) to handle duplicates correctly.
08Sum of Subarray RangesMedium
The range of a subarray is the difference between the largest and smallest element. Return the sum of all subarray ranges.
def subArrayRanges(self, nums: List[int]) -> int:
# Sum of max of all subarrays - Sum of min of all subarrays
return self.sumSubarrayMaxs(nums) - self.sumSubarrayMins(nums)O(n)O(n)Run Q907 twice - once for minimums, once for maximums. The range is the difference.
09Sliding Window MaximumHard
Given an array nums and sliding window size k, return the max sliding window.
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
dq = deque()
res = []
for i in range(n):
# Maintain monotonically decreasing deque
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()
dq.append(i)
# Window reached size k
if i >= k - 1:
res.append(nums[dq[0]])
if dq[0] == i - (k - 1):
dq.popleft()
return resO(n)O(k)Use monotonic deque. Front is always the maximum. Remove elements outside window.
10Number of Visible People in a QueueHard
A person can see another person to their right if everybody in between is shorter than both. Return how many people each person can see.
def canSeePersonsCount(self, heights: List[int]) -> List[int]:
n = len(heights)
stack = []
res = [0] * n
for i in range(n):
while stack and heights[stack[-1]] < heights[i]:
res[stack.pop()] += 1
if stack:
res[stack[-1]] += 1
stack.append(i)
return resO(n)O(n)NG template with a twist. When we pop, that person can see current person. The "if stack" handles when stack top is taller but can still see current person.
11Sum of Total Strength of WizardsHard
Total strength of a group = min(strength) × sum(strength). Return sum of total strengths of all contiguous groups.
def totalStrength(self, A: List[int]) -> int:
MOD = 10 ** 9 + 7
n = len(A)
# NLE on the right
right = [n] * n
stack = []
for i in range(n):
while stack and A[stack[-1]] >= A[i]:
right[stack.pop()] = i
stack.append(i)
# PL on the left
left = [-1] * n
stack = []
for i in range(n-1, -1, -1):
while stack and A[stack[-1]] > A[i]:
left[stack.pop()] = i
stack.append(i)
# Prefix sum of prefix sums for efficient range sum queries
prefix = list(accumulate(accumulate(A), initial=0))
res = 0
for i in range(n):
l, r = left[i], right[i]
# Sum of all subarrays where A[i] is minimum
# Left choices: (i - l), Right choices: (r - i)
left_sum = prefix[i + 1] * (r - i) - prefix[r + 1] * (i - l)
right_sum = prefix[i] * (r - i) - prefix[l] * (r - i)
contribution = (left_sum - right_sum) * A[i]
res = (res + contribution) % MOD
return res % MODO(n)O(n)Extension of Q907. Need prefix sum of prefix sums to efficiently compute sum of all subarray sums. Uses PL + NLE for contribution counting.
Complete Code Reference
Complete implementations for all 8 monotonic stack cases.
Previous Cases (iterate backwards)
PL, PLE, PG, PGE
# PL - Previous Less
def pl(A):
n = len(A)
stack = []
res = [-1] * n
for i in range(n-1, -1, -1):
while stack and A[stack[-1]] > A[i]:
res[stack.pop()] = i
stack.append(i)
return res
# PLE - Previous Less or Equal
def ple(A):
n = len(A)
stack = []
res = [-1] * n
for i in range(n-1, -1, -1):
while stack and A[stack[-1]] >= A[i]:
res[stack.pop()] = i
stack.append(i)
return res
# PG - Previous Greater
def pg(A):
n = len(A)
stack = []
res = [-1] * n
for i in range(n-1, -1, -1):
while stack and A[stack[-1]] < A[i]:
res[stack.pop()] = i
stack.append(i)
return res
# PGE - Previous Greater or Equal
def pge(A):
n = len(A)
stack = []
res = [-1] * n
for i in range(n-1, -1, -1):
while stack and A[stack[-1]] <= A[i]:
res[stack.pop()] = i
stack.append(i)
return resNext Cases (iterate forwards)
NL, NLE, NG, NGE
# NL - Next Less
def nl(A):
n = len(A)
stack = []
res = [n] * n
for i in range(n):
while stack and A[stack[-1]] > A[i]:
res[stack[-1]] = i
stack.pop()
stack.append(i)
return res
# NLE - Next Less or Equal
def nle(A):
n = len(A)
stack = []
res = [n] * n
for i in range(n):
while stack and A[stack[-1]] >= A[i]:
res[stack[-1]] = i
stack.pop()
stack.append(i)
return res
# NG - Next Greater
def ng(A):
n = len(A)
stack = []
res = [n] * n
for i in range(n):
while stack and A[stack[-1]] < A[i]:
res[stack[-1]] = i
stack.pop()
stack.append(i)
return res
# NGE - Next Greater or Equal
def nge(A):
n = len(A)
stack = []
res = [n] * n
for i in range(n):
while stack and A[stack[-1]] <= A[i]:
res[stack[-1]] = i
stack.pop()
stack.append(i)
return res