Advanced

Monotonic Stack

A monotonic stack maintains elements in strictly increasing or decreasing order. This pattern solves "next greater/smaller element" problems in O(n) time, replacing brute-force O(n²) approaches.

What is a Monotonic Stack?

# Monotonic Decreasing Stack (most common):
# Elements from bottom to top are in decreasing order.
# When a larger element arrives, pop smaller elements.
#
# Processing array [2, 1, 5, 6, 2, 3]:
#
#   Push 2:  stack = [2]
#   Push 1:  stack = [2, 1]     (1 < 2, maintain decreasing)
#   Push 5:  pop 1, pop 2       (5 > 1 and 5 > 2)
#            stack = [5]
#   Push 6:  pop 5              (6 > 5)
#            stack = [6]
#   Push 2:  stack = [6, 2]     (2 < 6, maintain decreasing)
#   Push 3:  pop 2              (3 > 2)
#            stack = [6, 3]
#
# Key insight: Each element is pushed and popped at most once -> O(n)

Problem 1: Next Greater Element I (LC 496)

Problem: Given two arrays nums1 (subset) and nums2, find the next greater element for each element in nums1 within nums2. Return -1 if no greater element exists.

# nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]
#
# For each element in nums2, find its next greater:
#   1 -> next greater is 3
#   3 -> next greater is 4
#   4 -> no next greater = -1
#   2 -> no next greater = -1
#
# Answer for nums1: [-1, 3, -1]
#
# Stack trace on nums2 = [1, 3, 4, 2]:
#   i=0, val=1: push 1             stack: [1]
#   i=1, val=3: pop 1 -> map[1]=3  stack: []
#               push 3             stack: [3]
#   i=2, val=4: pop 3 -> map[3]=4  stack: []
#               push 4             stack: [4]
#   i=3, val=2: push 2             stack: [4, 2]
#   End: remaining have no next greater

def nextGreaterElement(nums1, nums2):
    """Find next greater element using monotonic stack.

    Build a map: element -> its next greater in nums2.
    Then look up each element of nums1.

    Time:  O(n + m) where n=len(nums1), m=len(nums2)
    Space: O(m) for the map and stack
    """
    next_greater = {}
    stack = []

    for num in nums2:
        # Pop elements smaller than current
        while stack and stack[-1] < num:
            next_greater[stack.pop()] = num
        stack.append(num)

    # Remaining elements have no next greater
    return [next_greater.get(num, -1) for num in nums1]

Problem 2: Largest Rectangle in Histogram (LC 84)

Problem: Given an array of bar heights, find the largest rectangle area in the histogram.

# Heights: [2, 1, 5, 6, 2, 3]
#
# Visual histogram:
#            ___
#        ___|   |
#       |   |   |       ___
#  ___  |   |   |  ___ |   |
# |   | |   |   | |   ||   |
# | 2 | | 5 | 6 | | 2 || 3 |
# |___|_|___|___|_|___|_|___|
#   0   1   2   3   4   5
#
# Largest rectangle: height=5, width=2 (indices 2-3) = 10
#
# Stack approach: maintain increasing heights.
# When a shorter bar arrives, calculate areas for taller bars.
#
# Stack trace (indices):
#   i=0, h=2: push 0                   stack: [0]
#   i=1, h=1: pop 0, area=2*1=2        stack: []
#             push 1                    stack: [1]
#   i=2, h=5: push 2                   stack: [1, 2]
#   i=3, h=6: push 3                   stack: [1, 2, 3]
#   i=4, h=2: pop 3, area=6*1=6        stack: [1, 2]
#             pop 2, area=5*2=10        stack: [1]
#             push 4                    stack: [1, 4]
#   i=5, h=3: push 5                   stack: [1, 4, 5]
#   End: pop 5, area=3*1=3             stack: [1, 4]
#        pop 4, area=2*3=6             stack: [1]
#        pop 1, area=1*6=6             stack: []
#   Max area = 10

def largestRectangleArea(heights):
    """Find largest rectangle in histogram.

    Use a stack of indices. For each bar, when we find a
    shorter bar, pop and calculate the area using the
    popped bar's height and the width between boundaries.

    Time:  O(n) - each bar pushed/popped once
    Space: O(n) - stack size
    """
    stack = []  # stores indices
    max_area = 0
    heights.append(0)  # sentinel to flush remaining bars

    for i in range(len(heights)):
        while stack and heights[i] < heights[stack[-1]]:
            h = heights[stack.pop()]
            # Width: from stack top (left boundary) to i (right boundary)
            w = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, h * w)

        stack.append(i)

    heights.pop()  # remove sentinel
    return max_area

Problem 3: Maximal Rectangle (LC 85)

Problem: Given a 2D binary matrix filled with '0' and '1', find the largest rectangle containing only '1's.

# Matrix:
#   ["1","0","1","0","0"]
#   ["1","0","1","1","1"]
#   ["1","1","1","1","1"]
#   ["1","0","0","1","0"]
#
# Key insight: Treat each row as the base of a histogram.
# Build histogram heights row by row:
#
# Row 0: [1, 0, 1, 0, 0]  -> largest rect = 1
# Row 1: [2, 0, 2, 1, 1]  -> largest rect = 3
# Row 2: [3, 1, 3, 2, 2]  -> largest rect = 6  <-- answer
# Row 3: [4, 0, 0, 3, 0]  -> largest rect = 4
#
# For each row, apply "Largest Rectangle in Histogram"

def maximalRectangle(matrix):
    """Find largest rectangle of 1s in a binary matrix.

    Build histogram heights for each row, then apply
    the largest rectangle in histogram algorithm.

    Time:  O(rows * cols) - histogram per row
    Space: O(cols) - heights array
    """
    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 j in range(cols):
            if row[j] == '1':
                heights[j] += 1
            else:
                heights[j] = 0

        # Apply largest rectangle in histogram
        max_area = max(max_area, largestRectangleArea(heights[:]))

    return max_area

Problem 4: Online Stock Span (LC 901)

Problem: Design a class that collects daily stock prices and returns the span (number of consecutive days the price was less than or equal to today's price, including today).

# Prices:  [100, 80, 60, 70, 60, 75, 85]
# Spans:   [1,   1,  1,  2,  1,  4,  6]
#
# Day 0: price=100, no previous day         span=1
# Day 1: price=80,  80 < 100                span=1
# Day 2: price=60,  60 < 80                 span=1
# Day 3: price=70,  70 > 60                 span=2 (days 2-3)
# Day 4: price=60,  60 < 70                 span=1
# Day 5: price=75,  75 > 60, 75 > 70, 75 > 60  span=4 (days 2-5)
# Day 6: price=85,  85 > 75, 85 > 80        span=6 (days 1-6)
#
# Stack stores (price, span) pairs.
# When current price >= stack top, pop and accumulate span.

class StockSpanner:
    """Calculate stock span using a monotonic stack.

    Stack stores (price, span) tuples in decreasing price order.
    When a new price is >= stack top, pop and add their spans.

    Each call: O(1) amortized time
    Space: O(n) total for n calls
    """
    def __init__(self):
        self.stack = []  # (price, span)

    def next(self, price):
        span = 1

        # Pop all prices <= current price
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]

        self.stack.append((price, span))
        return span

Problem 5: Sum of Subarray Minimums (LC 907)

Problem: Given an array of integers, find the sum of min(subarray) for every contiguous subarray. Return the answer modulo 10^9 + 7.

# Input: arr = [3, 1, 2, 4]
#
# All subarrays and their minimums:
#   [3]       -> min = 3
#   [3,1]     -> min = 1
#   [3,1,2]   -> min = 1
#   [3,1,2,4] -> min = 1
#   [1]       -> min = 1
#   [1,2]     -> min = 1
#   [1,2,4]   -> min = 1
#   [2]       -> min = 2
#   [2,4]     -> min = 2
#   [4]       -> min = 4
#   Sum = 3+1+1+1+1+1+1+2+2+4 = 17
#
# Key insight: For each element arr[i], count how many
# subarrays have arr[i] as their minimum.
#
# For arr[i], find:
#   left[i]  = distance to previous smaller element
#   right[i] = distance to next smaller-or-equal element
#
# Number of subarrays where arr[i] is min = left[i] * right[i]
# Contribution = arr[i] * left[i] * right[i]

def sumSubarrayMins(arr):
    """Sum of minimums of all subarrays.

    Use two monotonic stacks to find:
    - Previous Less Element (PLE) distance for each index
    - Next Less-or-Equal Element (NLE) distance for each index

    Contribution of arr[i] = arr[i] * left[i] * right[i]

    Time:  O(n) - two passes with monotonic stacks
    Space: O(n) - stack and arrays
    """
    MOD = 10**9 + 7
    n = len(arr)
    left = [0] * n   # distance to previous smaller
    right = [0] * n  # distance to next smaller or equal
    stack = []

    # Find previous less element distances
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        left[i] = i - stack[-1] if stack else i + 1
        stack.append(i)

    # Find next less or equal element distances
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        right[i] = stack[-1] - i if stack else n - i
        stack.append(i)

    # Calculate total sum
    result = 0
    for i in range(n):
        result = (result + arr[i] * left[i] * right[i]) % MOD

    return result

Complexity Summary

Problem	Time	Space	Stack Type
Next Greater Element	O(n)	O(n)	Decreasing (pop on greater)
Largest Rectangle	O(n)	O(n)	Increasing (pop on shorter)
Maximal Rectangle	O(r×c)	O(c)	Histogram per row
Stock Span	O(1) amort.	O(n)	Decreasing (pop on >=)
Subarray Minimums	O(n)	O(n)	Two increasing stacks