Mastering Monotonic Stack Interview Problems: A Complete Guide

When you're in a coding interview and the interviewer asks you to find the next greater element for every element in an array, your heart might skip a beat. But what if you could solve it in O(n) time with a simple stack? That's the power of the monotonic stack pattern.

Monotonic stack is a technique where you maintain a stack that is either strictly increasing or decreasing. It's a go-to pattern for problems involving 'next greater', 'next smaller', 'previous greater', or 'previous smaller' elements. It also appears in more complex problems like 'Largest Rectangle in Histogram' and 'Trapping Rain Water'.

In this guide, we'll break down the monotonic stack pattern, walk through classic interview problems with detailed solutions, and share tips to ace your interview. By the end, you'll be able to recognize and solve monotonic stack problems with confidence.

What is a Monotonic Stack?

A monotonic stack is a stack that maintains its elements in a specific order — either strictly increasing or strictly decreasing. It's used to solve problems where you need to find the next greater or smaller element efficiently.

Types: - Increasing stack: Elements are in increasing order from bottom to top. Used for next smaller element. - Decreasing stack: Elements are in decreasing order. Used for next greater element.

How it works: You iterate through the array. For each element, you pop elements from the stack that violate the monotonic property. The popped elements' results are updated using the current element. Then you push the current element onto the stack.

Time Complexity: O(n) — each element is pushed and popped at most once. Space Complexity: O(n) — stack can hold up to n elements.

def next_greater_element(nums):
    n = len(nums)
    result = [-1] * n
    stack = []  # decreasing stack (store indices)
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    return result

# Example
print(next_greater_element([2, 1, 3, 4]))  # Output: [3, 3, 4, -1]

Classic Problem: Next Greater Element I

Problem: Given two arrays nums1 and nums2, where nums1 is a subset of nums2, find the next greater element for each element in nums1 within nums2.

Approach: Use a monotonic decreasing stack on nums2 to precompute next greater elements for all elements. Store in a hash map. Then answer for nums1 in O(1) each.

Steps: 1. Create a hash map next_greater. 2. Iterate through nums2 with a decreasing stack. 3. For each popped element, set its next greater to current element. 4. After loop, remaining elements have no next greater (store -1). 5. Build result for nums1 using the map.

Complexities: Time O(n + m), Space O(n).

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)
    for num in stack:
        next_greater[num] = -1
    return [next_greater[num] for num in nums1]

# Example
print(nextGreaterElement([4,1,2], [1,3,4,2]))  # Output: [-1,3,-1]

Classic Problem: Daily Temperatures

Problem: Given an array of temperatures, return an array such that answer[i] is the number of days you have to wait until a warmer temperature. If no warmer day, answer[i] = 0.

Approach: Use a decreasing stack of indices. When a warmer temperature is found, pop indices and compute the difference.

Steps: 1. Initialize result array with zeros. 2. Iterate through temperatures with index i. 3. While stack not empty and temperatures[stack[-1]] < temperatures[i]: - Pop index j. - result[j] = i - j. 4. Push i onto stack.

Complexities: Time O(n), Space O(n).

def dailyTemperatures(temperatures):
    n = len(temperatures)
    result = [0] * n
    stack = []
    for i in range(n):
        while stack and temperatures[stack[-1]] < temperatures[i]:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)
    return result

# Example
print(dailyTemperatures([73,74,75,71,69,72,76,73]))  # Output: [1,1,4,2,1,1,0,0]

Classic Problem: Largest Rectangle in Histogram

Problem: Given an array of bar heights, find the largest rectangle that can be formed in the histogram.

Approach: Use an increasing stack of indices. For each bar, pop bars taller than current, calculate area using current index as right boundary and the new top as left boundary.

Steps: 1. Append 0 to heights to handle remaining bars. 2. Iterate through heights with index i. 3. While stack not empty and heights[stack[-1]] > heights[i]: - Pop height h = heights[stack.pop()]. - Width = i if stack empty else i - stack[-1] - 1. - Update max area. 4. Push i.

Complexities: Time O(n), Space O(n).

def largestRectangleArea(heights):
    stack = []
    max_area = 0
    heights.append(0)  # sentinel
    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)
    heights.pop()
    return max_area

# Example
print(largestRectangleArea([2,1,5,6,2,3]))  # Output: 10

Classic Problem: Trapping Rain Water

Problem: Given an array of non-negative integers representing elevation, compute how much water can be trapped after rain.

Approach: Use a decreasing stack. When a bar taller than the top is found, pop the top as a valley, and calculate water trapped using the new top as left boundary and current as right boundary.

Steps: 1. Initialize stack and water = 0. 2. Iterate through heights with index i. 3. While stack not empty and heights[stack[-1]] < heights[i]: - Pop top = stack.pop(). - If stack empty, break. - Distance = i - stack[-1] - 1. - Bounded height = min(heights[stack[-1]], heights[i]) - heights[top]. - Water += distance * bounded height. 4. Push i.

Complexities: Time O(n), Space O(n).

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

# Example
print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))  # Output: 6

Advanced Problem: Sum of Subarray Minimums

Problem: Given an array, find the sum of minimums of all contiguous subarrays. Return result modulo 10^9+7.

Approach: For each element, find how many subarrays it is the minimum of. Use two passes with monotonic stack: one for previous smaller element (PSE) and one for next smaller element (NSE).

Steps: 1. Compute left[i] = distance to previous smaller element (strictly smaller). 2. Compute right[i] = distance to next smaller element (strictly smaller). 3. For each i, contribution = arr[i] left[i] right[i]. 4. Sum all contributions modulo MOD.

Complexities: Time O(n), Space O(n).

def sumSubarrayMins(arr):
    MOD = 10**9 + 7
    n = len(arr)
    left = [0] * n
    right = [0] * n
    stack = []
    # Previous smaller
    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)
    stack.clear()
    # Next smaller
    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)
    result = 0
    for i in range(n):
        result = (result + arr[i] * left[i] * right[i]) % MOD
    return result

# Example
print(sumSubarrayMins([3,1,2,4]))  # Output: 17

Interview Tips and Variations

Recognizing the Pattern: - Problem asks for 'next greater/smaller', 'previous greater/smaller', or 'nearest greater/smaller'. - Problem involves calculating something based on the nearest larger or smaller element. - Examples: Stock span, sliding window maximum (can use deque), maximum of minimums of every window size.

Common Variations: - Next Greater Element II (circular array): iterate twice. - Online Stock Span: maintain stack of (price, span). - Maximum Width Ramp: use decreasing stack of indices.

Interview Communication: 1. Start with brute force O(n²) and explain why it's suboptimal. 2. Introduce monotonic stack as optimization. 3. Walk through an example with a small array. 4. Discuss edge cases: empty, duplicates, decreasing/increasing order. 5. Analyze time and space complexity.

Common Mistakes: - Using wrong monotonic property (increasing vs decreasing). - Forgetting to handle remaining elements in stack. - Off-by-one errors in width calculations.