2 Monotonic Stack Pattern - LeetCode Patterns

Monotonic Stack Pattern

A Monotonic Stack is a stack that maintains elements in either strictly increasing or strictly decreasing order. This pattern is used to find the next greater/smaller element efficiently.

When to Use This Pattern

  • Finding next greater/smaller element
  • Finding previous greater/smaller element
  • Problems involving temperature, stock prices, or heights
  • Largest rectangle in histogram problems

Key Concepts

  • Monotonically Increasing: Elements increase from bottom to top
  • Monotonically Decreasing: Elements decrease from bottom to top

Algorithm Section

Next Greater Element

function nextGreaterElement(nums):
    stack = []
    result = [-1] * len(nums)
    
    for i in range(len(nums)):
        while stack and nums[stack[-1]] < nums[i]:
            index = stack.pop()
            result[index] = nums[i]
        stack.append(i)
    
    return result

Practice Problems

Problem 1: Next Greater Element I (LeetCode #496)

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.

Solution:

def nextGreaterElement(nums1, nums2):
    stack = []
    next_greater = {}
    
    for num in nums2:
        while stack and stack[-1] < num:
            next_greater[stack.pop()] = num
        stack.append(num)
    
    return [next_greater.get(num, -1) for num in nums1]

Explanation: We use a decreasing monotonic stack. When we find a number greater than the top, we pop and record the next greater element. This efficiently finds next greater elements for all numbers.

Time Complexity: O(n + m)

Space Complexity: O(n)

Problem 2: Daily Temperatures (LeetCode #739)

Given an array of integers temperatures representing the 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.

Solution:

def dailyTemperatures(temperatures):
    stack = []
    result = [0] * len(temperatures)
    
    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            prev_index = stack.pop()
            result[prev_index] = i - prev_index
        stack.append(i)
    
    return result

Explanation: We maintain a decreasing stack of indices. When we find a warmer day, we pop previous days and calculate the difference in indices. This gives us the number of days to wait.

Time Complexity: O(n)

Space Complexity: O(n)

Problem 3: Largest Rectangle in Histogram (LeetCode #84)

Given an array of integers heights representing the histogram's bar height, return the area of the largest rectangle in the histogram.

Solution:

def largestRectangleArea(heights):
    stack = []
    max_area = 0
    
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    
    while stack:
        height = heights[stack.pop()]
        width = len(heights) if not stack else len(heights) - stack[-1] - 1
        max_area = max(max_area, height * width)
    
    return max_area

Explanation: We use an increasing stack. When we find a bar shorter than the top, we calculate the area of rectangles ending at that bar. The width is determined by the positions where the height can extend.

Time Complexity: O(n)

Space Complexity: O(n)

Problem 4: Trapping Rain Water (LeetCode #42)

Given n non-negative integers representing an elevation map, compute how much water it can trap after raining.

Solution:

def trap(height):
    stack = []
    water = 0
    
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()
            if not stack:
                break
            width = i - stack[-1] - 1
            trapped_height = min(height[stack[-1]], h) - height[bottom]
            water += width * trapped_height
        stack.append(i)
    
    return water

Explanation: We use a decreasing stack. When we find a bar higher than the top, we can trap water. We calculate the trapped water between the current bar, the popped bar, and the new top of the stack.

Time Complexity: O(n)

Space Complexity: O(n)

Problem 5: Remove K Digits (LeetCode #402)

Given string num representing a non-negative integer and an integer k, return the smallest possible integer after removing k digits.

Solution:

def removeKdigits(num, k):
    stack = []
    
    for digit in num:
        while stack and k > 0 and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    
    # Remove remaining k digits from end
    while k > 0:
        stack.pop()
        k -= 1
    
    # Remove leading zeros
    result = ''.join(stack).lstrip('0')
    return result if result else '0'

Explanation: We maintain an increasing stack. We remove digits that are larger than the current digit (greedy). This ensures we keep the smallest digits. After processing, we remove any remaining k digits from the end.

Time Complexity: O(n)

Space Complexity: O(n)