Templates for monotonic stacks and queues (with solved problems)

4374

Apr 28, 2024

Template introductions for monotonic stacks and queues:

Monotonic stacks and queues used to be incomprehensible to me, but now I find them to be quite cool. The DSA LeetCode Crash Course was really helpful as a starting point in working through a number of different problems related to monotonic stacks and queues (can't recommend enough!). I thought I'd share some of the more helpful templates I ended up coming up with as well as some solutions to problems by using the templates (the original post I was writing turned out to be way too long to post on LeetCode's platform directly!).

Four templates are presented below:

Template for finding A's next value B (i.e., next larger/smaller (or equal) value).

From what I've seen, this is probably the most common basic use case for monotonic stacks. LC 739. Daily Temperatures is a good example where this can be used.
Template for finding A's previous value B (i.e., previous larger/smaller (or equal) value).

Using monotonic stacks in the context of finding "previous" value relations seems to be less common than the "next" value kinds of problems, but this can still be relevant in problems like LC 901. Online Stock Span, LC 907. Sum of Subarray Minimums, LC 2104. Sum of Subarray Ranges, etc.
Combined templates for finding previous and next values in a single pass

This is really neat: it turns out you can process all values in an array in one pass where the outcome is knowing each value's next AND previous smaller/larger (or equal) value based on what kind of monotonic stack you're maintaining (i.e., strictly decreasing, weakly decreasing, strictly increasing, weakly increasing).

The key is realizing that usually when you're maintaining the monotonic invariant for a stack, each value popped from the stack has the current value we're about to add to the stack as its next value in some capacity (e.g., if we're maintaining a strictly decreasing stack and we just had to pop 4 to make room for 6, then 4 has 6 as its next larger or equal value -- the template will explain this more clearly, but the point is that each popped value has the current value as its next value in some comparative way). Once all values have been popped from the stack to make way for the current value we're about to add, we can actually determine the current value's previous value in some comparative capacity by looking at the rightmost/top value still in the stack (if there is one; if there isn't one, then the current value has no previous value of a certain comparative nature based on what kind of stack is being maintained). For example, if we're maintaining a strictly decreasing stack whose state is currently [9, 7, 4] and we're about to add a 6, then we first pop the 4, and the rightmost/top value still in the stack is 7 -- this means 6 has 7 as its previous larger value (the template will show all of this too).

The stuff above can be confusing at first, but the main/cool takeaway is that for each value we're about to add to the stack, we can do two things: determine all the next values for elements popped off the stack and determine the previous value for the element we're about to add to the stack. This can be very powerful in coming up with easy-to-understand optimial solutions to otherwise quite difficult problems like LC 907. Sum of Subarray Minimums and LC 2104. Sum of Subarray Ranges.
Monotonic deque (weakly decreasing)

Using a monotonic deque is almost the same as using a monotonic stack -- stack-like operations are used for both data structures to maintain each collection's monotonic invariant, but sometimes a deque is needed to be able to efficiently remove values from the left. This becomes relevant when values in the stack can become invalidated after the addition of new values. Sliding windows are a classic example of this. LC 239. Sliding Window Maximum is a good example where a monotonic deque can be used effectively.

Template for finding A's next value B:

def fn(nums):
    n = len(nums)
    ans = [None] * n
    stack = [] # monotonic stack
    for i in range(n):
        val_B = nums[i]
        # the comparison operator (?) dictates what A's next value B represents
        # (<)  next larger value (weakly decreasing stack)
        # (<=) next larger or equal value (strictly decreasing stack)
        # (>)  next smaller value (weakly increasing stack)
        # (>=) next smaller or equal value (strictly increasing stack)
        while stack and nums[stack[-1]] ? val_B:
            idx_val_A = stack.pop()
            ans[idx_val_A] = val_B
        stack.append(i)
    
    # process elements that never had a "next" value that satisfied the criteria
    while stack:
        idx_val_A = stack.pop()
        ans[idx_val_A] = -1
    
    return ans

Template for finding A's previous value B:

def fn(nums):
    n = len(nums)
    ans = [None] * n
    stack = [] # monotonic stack
    for i in range(n):
        val_A = nums[i]
        # the comparison operator (?) dictates what A's previous value B represents
        # (<=) previous larger (strictly decreasing)
        # (<)  previous larger or equal value (weakly decreasing)
        # (>=) previous smaller value (strictly increasing)
        # (>)  previous smaller or equal value (weakly increasing)
        while stack and nums[stack[-1]] ? val_A:
            stack.pop()
            
        if stack:
            idx_val_B = stack[-1]
            val_B = nums[idx_val_B]
            ans[i] = val_B
        else:
            ans[i] = -1
        
        stack.append(i)
        
    return ans

Combined templates for finding previous and next values in a single pass:

def fn(nums):
    n = len(nums)
    ans = [[-1, -1] for _ in range(n)] # default values for missing PREVIOUS and NEXT values, respectively
    stack = [] # monotonic stack
    
    # the comparison operator (?) dictates what each element's PREVIOUS and NEXT values will be
    # (<=) PREVIOUS larger value and NEXT larger or equal value (strictly decreasing stack)
    # (<)  PREVIOUS larger or equal value and NEXT larger value (weakly decreasing stack)
    # (>=) PREVIOUS smaller value and NEXT smaller or equal value (strictly increasing stack)
    # (>)  PREVIOUS smaller or equal value and NEXT smaller value (weakly increasing stack)
    for i in range(n):
        while stack and nums[stack[-1]] ? nums[i]:
            # NEXT values processed
            idx = stack.pop()
            ans[idx][1] = i # use nums[i] instead of i to directly record array values instead of indexes
        # PREVIOUS values processed
        ans[i][0] = -1 if not stack else stack[-1] # use nums[stack[-1]] instead of stack[-1] 
                                                   # to directly record array values instead of indexes 
        stack.append(i)
    
    return ans

Monotonic deque (weakly decreasing):

from collections import deque
def fn(nums):
    queue = deque() # monotonic deque (weakly decreasing)
    ans = []
    
    for i in range(len(nums)):
        curr_num = nums[i]
        while queue and nums[queue[-1]] < curr_num:
            queue.pop()
        queue.append(i)
        
        if CONDITION:
            queue.popleft()
        
    return ans

Note about monotonic deque "template"

The code in the template above is virtually the same as the code used to maintain a monotonic stack (weakly decreasing) with one notable exception:

def fn(nums):
    dec_stack = []
    ans = []
    
    for i in range(len(nums)):
        curr_num = nums[i]
        while dec_stack and nums[dec_stack[-1]] < curr_num:
            dec_stack.pop()
        dec_stack.append(i)


    # no condition is used to remove elements here
    # when just using a plain monotonic stack


    return ans

Solved problems (links):

Solved problems (solutions):

LC 739. Daily Temperatures

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        ans = [None] * n
        stack = []
        
        for i in range(n):
            val_A = temperatures[i]
            # try to find the next larger temperature, val_B,
            # for the current temperature, val_A
            while stack and temperatures[stack[-1]] < val_A:
                idx_val_B = stack.pop()
                ans[idx_val_B] = i - idx_val_B
            stack.append(i)
        
        # remaining temperatures, val_A, have no next larger temperature, val_B
        while stack:
            idx_val_A = stack.pop()
            ans[idx_val_A] = 0
            
        return ans

The approach above is almost a direct application of the template for next value problems, where we're trying to find the next larger value for each value we encounter. We use the difference in indexes to determine how many days there are to wait.

LC 239. Sliding Window Maximum

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        dec_queue = deque() # monotonic deque (weakly decreasing)
        ans = []
        for i in range(n):
            curr_num = nums[i]
            # maintain the weakly decreasing deque
            while dec_queue and nums[dec_queue[-1]] < curr_num:
                dec_queue.pop()
            
            # check to see if leftmost value of the deque
            # is now actually an invalid index
            if dec_queue and dec_queue[0] == i - k:
                dec_queue.popleft()
            
            dec_queue.append(i)
            
            # only add window maximums to the answer array
            # once the required length has been reached
            if i >= k - 1:
                ans.append(nums[dec_queue[0]])
                
        return ans

We're not trying to find a "next" or "previous" anything. We're trying to maintain a sliding window maximum. A monotonic deque that is weakly decreasing is the tool of choice here (weakly decreasing instead of strictly since the same window can have duplicated maxima) since access to the leftmost element will always be the maximum. Additionally, if sliding the window results in invalidating the leftmost index of the deque pointing to the maximum, then we can simply pop from the left.

LC 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        n = len(nums)
        dec_queue = deque() # monotonic deque (weakly decreasing) for the maximums
        inc_queue = deque() # monotonic deque (weakly increasing) for the minimums
        left = ans = 0
        
        for right in range(n):
            curr_num = nums[right]
            
            # maintain the deque invariants
            while dec_queue and nums[dec_queue[-1]] < curr_num:
                dec_queue.pop()
            while inc_queue and nums[inc_queue[-1]] > curr_num:
                inc_queue.pop()
                
            dec_queue.append(right)
            inc_queue.append(right)
                
            # update sliding window to ensure the window is valid
            while left <= right and nums[dec_queue[0]] - nums[inc_queue[0]] > limit:
                # remove possibly invalidated indexes from the deques once the window has shifted
                if dec_queue[0] == left:
                    dec_queue.popleft()
                if inc_queue[0] == left:
                    inc_queue.popleft()
                left += 1

            # update the answer with the length of the current valid window
            ans = max(ans, right - left + 1)
        
        return ans

We're not trying to find a "next" or "previous" anything. We need to somehow process all subarrays to find the longest one such that the absolute difference between any two elements in the subarray is less than or equal to limit. The absolute difference is biggest (and thus threatens to exceed limit) when we take the difference between the subarray's maximum and its minimum. Hence, we're essentially trying to maintain a subarray's maximum and minimum. The previous practice problem, LC 239, showed how to artfully handle maintaining a sliding window maximum. We employ similar logic here to maintain a sliding window maximum and minimum. Two deques are needed in order to do this effectively.

LC 496. Next Greater Element I

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        queries = {}
        stack = []
        
        # determine "next greater" values in nums2
        for i in range(len(nums2)):
            val_B = nums2[i]
            while stack and nums2[stack[-1]] < val_B:
                idx_val_A = stack.pop()
                val_A = nums2[idx_val_A]
                queries[val_A] = val_B
            stack.append(i)
        
        # remaining values have no next greater value (default to -1)
        while stack:
            idx_val_A = stack.pop()
            val_A = nums2[idx_val_A]
            queries[val_A] = -1
            
        # the queries hash map tells us the next greater value
        # for each value queried from nums1
        ans = [None] * len(nums1)
        for i in range(len(nums1)):
            ans[i] = queries[nums1[i]]
            
        return ans

The framing for this problem is somewhat odd at first. Nonetheless, once we can wrap our heads around what exactly is being asked, our approach is almost a direct application of the template for next value problems (specifically next greater value, of course). The code above can be cleaned up a little by using defaultdict from the collections module and not adhering so closely to the syntax of the template:

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        queries = defaultdict(lambda: -1)
        stack = []
        
        for i in range(len(nums2)):
            val_B = nums2[i]
            while stack and nums2[stack[-1]] < val_B:
                idx_val_A = stack.pop()
                val_A = nums2[idx_val_A]
                queries[val_A] = val_B
            stack.append(i)
        
        ans = [None] * len(nums1)
        for i in range(len(nums1)):
            ans[i] = queries[nums1[i]]
            
        return ans

LC 503. Next Greater Element II

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [None] * n
        stack = []
        
        for i in range(n * 2):
            val_B = nums[i % n]
            while stack and nums[stack[-1]] < val_B:
                idx_val_A = stack.pop()
                ans[idx_val_A] = val_B

            # only add elements to the stack on the first full pass
            if i < n:
                stack.append(i)
            else:
                # otherwise the remaining values (if there are any)
                # never had a next greater element; hence, we simply
                # make another full pass to see if any element is greater
                # than the current element in the stack and then pop the
                # element from the stack if the answer is affirmative
                if stack and nums[stack[-1]] < nums[i % n]:
                    idx_val_A = stack.pop()
                    ans[idx_val_A] = nums[i % n]
        
        # the remaining values in the stack are those that do not have a next
        # greater element despite two full passes; we report -1 for these values
        while stack:
            idx_val_A = stack.pop()
            ans[idx_val_A] = -1
            
        return ans

This problem is the same as LC 496, but there's a significant twist where now we're considering the array to be circular. This may sound wild at first, but the change in approach is actually quite simple: we can cycle back through the original array by iterating a total of 2 * n times where n = len(nums). To ensure we don't get an "index out of bounds" error, we use a standard trick, namely the modulus operator %: i % n. Hence, if n = 10, and i = 10, then we're really looking at the element at index i = 0 since 10 % 10 == 0.

The approach above is a slightly tweaked application of the template for next value problems.

LC 901. Online Stock Span

class StockSpanner:
    def __init__(self):
        self.stack = []
        self.idx = 0

    def next(self, price: int) -> int:
        val_A = price
        while self.stack and self.stack[-1][0] <= price:
            self.stack.pop()
            
        if self.stack:
            idx_val_B = self.stack[-1][1]
            val_B = self.stack[-1][0]
            stock_span = self.idx - idx_val_B
        else:
            stock_span = self.idx + 1
            
        self.stack.append([val_A, self.idx])
        self.idx += 1
        
        return stock_span

The approach above is almost a direct application of the template for previous value problems, where we're finding the previous larger value. It's not necessary to use the val_A/val_B nomenclature in the solution above — it's simply done to show how similar an acceptable solution is to the bare bones previous value template.

Why are we interested in finding the previous larger value for each new value we encounter? Because the stock span of the new/current value is effectively defined as the total number of previous less than or equal to values. Finding the previous larger value tells us where the current value's stock span begins.

LC 1475. Final Prices With a Special Discount in a Shop

class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        n = len(prices)
        stack = []
        
        for i in range(n):
            val_B = prices[i]
            while stack and prices[stack[-1]] >= val_B:
                idx_val_A = stack.pop()
                prices[idx_val_A] -= val_B # val_B is discount since it is next less or equal value to val_A
            stack.append(i)
        
        return prices

The approach above is almost a direct application of the template for next value problems, specifically the "next less or equal value" problem. For each price, we want to determine if we can obtain a discount, and a discount is only possible if a subsequent value is less than or equal to the current value, hence the approach outlined above.

LC 1063. Number of Valid Subarrays

class Solution:
    def validSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        queries = [n] * n
        stack = []
        ans = 0
        
        for i in range(n):
            val_B = nums[i]
            while stack and nums[stack[-1]] > val_B:
                idx_val_A = stack.pop()
                queries[idx_val_A] = i
            stack.append(i)
        
        # query the next smaller value for each index of nums
        # the current index will be the included left endpoint 
        # and the queried value will be the excluded right endpoint
        # total number of subarrays contributed where the left endpoint
        # is the minimum: right - left (since right is excluded)
        for left in range(n):
            right = queries[left]
            ans += right - left # NOT "right - left + 1" because right is not included here
        
        return ans

The template for next value problems is valuable here since we're effectively looking for each value's "next smaller" value. Why? Because until we've found the current value's next smaller value, the current value is the minimum value (there may be other equal minimum values that contribute to the subarray count).

The deeper intuition for solving this problem strongly depends on understanding that if the window [left, right] and all its "sub-windows" satisfy some constraint for a subarray (i.e., leftmost element being minimal in this problem), then the number of valid subarrays is given by right - left + 1.

Brief explanation for number of valid subarrays being right - left + 1

If the subarray [left, right] and all its subarrays are valid, then how many such valid subarrays are there? This number is given by right - left + 1. Why? Because this number gives us the number of subarrays that end at index right:

[left, right]
[left + 1, right]
[left, + 2, right]
...
[right - 1, right]
[right, right] (single element, right)

The idea is that we can fix the right bound and then choose any value between left and right, inclusive, for the left bound such that the newly bounded subarray is valid. The total number of values to choose from is the length of the [left, right] subarray: right - left + 1.

LC 1673. Find the Most Competitive Subsequence

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        stack = []
        
        for i in range(n):
            curr_num = nums[i]
            while stack and stack[-1] > curr_num and (n - i + len(stack) > k):
                stack.pop()
            
            if len(stack) < k:
                stack.append(nums[i])
        
        return stack

This is a really neat monotonic stack problem because the monotonic stack itself serves as part (or all) of the solution. The intuition is that the most competitive subsequence will be the one whose leftmost elements are as small as possible. A weakly increasing monotonic stack is almost all we need, but the main wrinkle for this problem is that the subsequence we return must be of length k. Hence, the goal effectively becomes the following: use a weakly increasing monotonic stack "as long as possible" (to ensure its leftmost elements are as small as possible) until we're forced to indiscriminately add elements in order to reach the required size of k.

Providing code comments may help in order to see the logic outlined above more clearly:

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        stack = [] # monotonic stack (weakly increasing)
        
        for i in range(n):
            curr_num = nums[i]
            # number of elements remaining in nums (including curr_num): n - i
            # current number of elements in stack: len(stack)
            # goal: stack must ultimately have a total of k elements; hence,
            #   only consider popping an element from the stack if there are enough remaining
            #   elements in nums to ensure the final size of the stack is k
            while stack and stack[-1] > curr_num and (n - i + len(stack) > k):
                stack.pop()
            
            # the stack should never exceed k elements
            if len(stack) < k:
                stack.append(nums[i])
        
        return stack

LC 2398. Maximum Number of Robots Within Budget

class Solution:
    def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
        dec_queue = deque() # monotonic deque (weakly decreasing) for charge times
        left = window_sum = ans = 0
        
        for right in range(len(chargeTimes)):
            # maintain monotonic deque to ensure maximum charge time in window is quickly accessible
            curr_charge = chargeTimes[right]
            while dec_queue and chargeTimes[dec_queue[-1]] < curr_charge:
                dec_queue.pop()
            dec_queue.append(right)
            
            # maintain total running cost of sliding window
            curr_running_cost = runningCosts[right]
            window_sum += curr_running_cost
            
            while left <= right and dec_queue and chargeTimes[dec_queue[0]] + (right - left + 1) * window_sum > budget:
                # adjust window_sum to reflect new sliding window's total running cost
                window_sum -= runningCosts[left]
                # remove leftmost queue element if index is no longer valid after shifting window
                if dec_queue[0] == left:
                    dec_queue.popleft()
                left += 1
            
            ans = max(ans, right - left + 1)
            
        return ans

Arguably one of the hardest parts of this problem is fully understanding the problem statement itself. Specifically, the total cost formula max(chargeTimes) + k * sum(runningCosts) is somewhat confusing since realistically there's no need to multiply the sum of running costs by k; nonetheless, the problem statement dictates that the total cost formula stands as detailed above — we must use it in our solution.

Since the robots being used as part of the solution ultimately must be consecutive, this is a hint that a sliding window may be relevant. Since we always need the maximum of the charge values for the robots being used, it seems like we will need to maintain a sliding window maximum, which is where a monotonic deque can shine. A weakly decreasing monotonic deque should be used since a sliding window's maximum may not be unique. The rest of the problem then simply becomes maintaining the monotonic deque effectively while sliding the window (and maintaining the window sum as well for the total running cost).

LC 907. Sum of Subarray Minimums

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        def minimum_boundaries(nums):
            n = len(nums)
            # missing previous values assigned as -1 (just before leftmost boundary)
            # missing next values assigned as n (just after rightmost boundary)
            ans = [[-1, n] for _ in range(n)]
            stack = [] # monotonic stack
            
            # the comparison operator (?) dictates what each element's PREVIOUS and NEXT values will be
            # (>=) PREVIOUS smaller value and NEXT smaller or equal value (strictly increasing stack)
            #       (good for finding minimums, non-strict to left and strict to right)
            # (>)  PREVIOUS smaller or equal value and NEXT smaller value (weakly increasing stack)
            #       (good for finding minimums, strict to left and non-strict to right)
            for i in range(n):
                while stack and nums[stack[-1]] > nums[i]: # either >= or > will work here
                    idx = stack.pop()
                    ans[idx][1] = i
                ans[i][0] = -1 if not stack else stack[-1]
                stack.append(i)
            return ans
        
        min_bounds_lookup = minimum_boundaries(arr)
        ans = 0
        MOD = 10 ** 9 + 7
        
        for i in range(len(arr)):
            left_boundary, right_boundary = min_bounds_lookup[i]
            num_subarrays = (i - left_boundary) * (right_boundary - i)
            contribution = arr[i] * num_subarrays
            ans += contribution
            
        return ans % MOD

This is almost a direct application of the template to find previous and next values, but the solution on LeetCode's article fleshes out more of why some of the other logic is needed.

LC 2104. Sum of Subarray Ranges

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        def minimum_boundaries(nums):
            n = len(nums)
            # missing previous values assigned as -1 (just before leftmost boundary)
            # missing next values assigned as n (just after rightmost boundary)
            ans = [[-1, n] for _ in range(n)]
            stack = [] # monotonic stack
            
            # the comparison operator (?) dictates what each element's PREVIOUS and NEXT values will be
            # (>=) PREVIOUS smaller value and NEXT smaller or equal value (strictly increasing stack)
            #       (good for finding minimums, non-strict to left and strict to right)
            # (>)  PREVIOUS smaller or equal value and NEXT smaller value (weakly increasing stack)
            #       (good for finding minimums, strict to left and non-strict to right)
            for i in range(n):
                while stack and nums[stack[-1]] > nums[i]: # either >= or > will work here
                    idx = stack.pop()
                    ans[idx][1] = i
                ans[i][0] = -1 if not stack else stack[-1]
                stack.append(i)
            return ans

        def maximum_boundaries(nums):
            n = len(nums)
            # missing previous values assigned as -1 (just before leftmost boundary)
            # missing next values assigned as n (just after rightmost boundary)
            ans = [[-1, n] for _ in range(n)]
            stack = [] # monotonic stack
            
            # the comparison operator (?) dictates what each element's PREVIOUS and NEXT values will be
            # (<=) PREVIOUS larger value and NEXT larger or equal value (strictly decreasing stack)
            #       (good for finding maximums, non-strict to left and strict to right)
            # (<)  PREVIOUS larger or equal value and NEXT larger value (weakly decreasing stack)
            #       (good for finding maximums, strict to left and non-strict to right)
            for i in range(n):
                while stack and nums[stack[-1]] < nums[i]: # either <= or < will work here
                    idx = stack.pop()
                    ans[idx][1] = i
                ans[i][0] = -1 if not stack else stack[-1]
                stack.append(i)
            return ans
        
        min_bounds_lookup = minimum_boundaries(nums)
        max_bounds_lookup = maximum_boundaries(nums)
        ans = 0
        
        for i in range(len(nums)):
            min_left_boundary, min_right_boundary = min_bounds_lookup[i]
            max_left_boundary, max_right_boundary = max_bounds_lookup[i]
            num_min_subarrays = (i - min_left_boundary) * (min_right_boundary - i)
            num_max_subarrays = (i - max_left_boundary) * (max_right_boundary - i)
            contribution = nums[i] * num_max_subarrays - nums[i] * num_min_subarrays
            ans += contribution
            
        return ans

This is almost a direct application of the template to find previous and next values (except we use it twice, once for minimum boundaries and then again for maximum boundaries), but the solution on LeetCode's article fleshes out more of why some of the other logic is needed.

Comments (0)