In the world of competitive programming and technical interviews, particularly for positions at major tech companies like FAANG (Facebook, Amazon, Apple, Netflix, Google), mastering advanced data structures and algorithms is crucial. One such powerful tool that often comes in handy is the monotonic stack. In this comprehensive guide, we’ll explore when and why you should consider using a monotonic stack, along with practical examples and implementation details.

What is a Monotonic Stack?

Before diving into the use cases, let’s first understand what a monotonic stack is. A monotonic stack is a stack that maintains either a strictly increasing or strictly decreasing order of elements. This property makes it incredibly useful for solving a variety of problems efficiently.

There are two types of monotonic stacks:

  • Monotonic Increasing Stack: Each element in the stack is greater than or equal to the element below it.
  • Monotonic Decreasing Stack: Each element in the stack is smaller than or equal to the element below it.

When to Use a Monotonic Stack

Now that we understand what a monotonic stack is, let’s explore the scenarios where it can be particularly useful:

1. Next Greater/Smaller Element Problems

One of the most common applications of a monotonic stack is solving “next greater element” or “next smaller element” problems. These problems typically ask you to find the next greater (or smaller) element for each element in an array.

Example Problem: Given an array of integers, find the next greater element for each element. The next greater element is the first element to the right that is greater than the current element.

For this type of problem, a monotonic decreasing stack is ideal. Here’s how it works:

  1. Iterate through the array from left to right.
  2. For each element, while the stack is not empty and the current element is greater than the top of the stack:
    • Pop the top element from the stack.
    • Set the next greater element for the popped element to be the current element.
  3. Push the current element onto the stack.

Here’s a Python implementation of this approach:

def next_greater_element(arr):
    n = len(arr)
    result = [-1] * n  # Initialize result array with -1
    stack = []

    for i in range(n - 1, -1, -1):
        while stack and stack[-1] <= arr[i]:
            stack.pop()
        
        if stack:
            result[i] = stack[-1]
        
        stack.append(arr[i])

    return result

# Example usage
arr = [4, 5, 2, 10, 8]
print(next_greater_element(arr))  # Output: [5, 10, 10, -1, -1]

2. Histogram Problems

Monotonic stacks are particularly useful for solving problems related to histograms, such as finding the largest rectangle area in a histogram.

Example Problem: Given an array of integers representing the height of bars in a histogram, find the area of the largest rectangle that can be formed in the histogram.

For this problem, we can use a monotonic increasing stack to keep track of the indices of the bars. The idea is to calculate the area with every bar as the smallest bar in the rectangle:

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    heights.append(0)  # Add a sentinel value to handle the last bar

    for i, h in enumerate(heights):
        start = i
        while stack and stack[-1][1] > h:
            index, height = stack.pop()
            max_area = max(max_area, height * (i - index))
            start = index
        stack.append((start, h))

    return max_area

# Example usage
heights = [2, 1, 5, 6, 2, 3]
print(largest_rectangle_area(heights))  # Output: 10

3. Temperature Problems

Problems involving daily temperatures or similar scenarios where you need to find the number of days until a warmer (or cooler) temperature can be efficiently solved using a monotonic stack.

Example Problem: Given an array of integers representing daily temperatures, return an array such that, for each day, it tells you how many days you have to wait until a warmer temperature.

def daily_temperatures(temperatures):
    n = len(temperatures)
    result = [0] * n
    stack = []

    for i in range(n - 1, -1, -1):
        while stack and temperatures[stack[-1]] <= temperatures[i]:
            stack.pop()
        
        if stack:
            result[i] = stack[-1] - i
        
        stack.append(i)

    return result

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

4. Stock Span Problems

Stock span problems, which involve finding the number of consecutive days before the current day where the stock price was less than or equal to the current day’s price, can be efficiently solved using a monotonic stack.

Example Problem: Given an array of daily stock prices, calculate the span of each day’s stock price. The span of a stock’s price on a given day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price on that given day.

def stock_span(prices):
    n = len(prices)
    spans = [1] * n
    stack = []

    for i in range(n):
        while stack and prices[stack[-1]] <= prices[i]:
            spans[i] += spans[stack.pop()]
        stack.append(i)

    return spans

# Example usage
prices = [100, 80, 60, 70, 60, 75, 85]
print(stock_span(prices))  # Output: [1, 1, 1, 2, 1, 4, 6]

Advantages of Using Monotonic Stacks

Now that we’ve seen some examples of when to use monotonic stacks, let’s discuss their advantages:

  1. Time Complexity: Monotonic stacks often provide a linear time complexity (O(n)) solution for problems that might otherwise require a quadratic time complexity (O(n^2)) with naive approaches.
  2. Space Efficiency: While they do use additional space, the space complexity is typically O(n) in the worst case, which is often acceptable given the time savings.
  3. Versatility: Monotonic stacks can be applied to a wide range of problems, making them a valuable tool in a programmer’s arsenal.
  4. Elegance: Solutions using monotonic stacks are often more elegant and concise compared to other approaches.

Implementing a Monotonic Stack

Implementing a monotonic stack is straightforward. In most programming languages, you can use the built-in stack data structure (or a list/array that you use as a stack) and maintain the monotonic property while pushing and popping elements.

Here’s a generic implementation of a monotonic increasing stack in Python:

class MonotonicIncreasingStack:
    def __init__(self):
        self.stack = []

    def push(self, x):
        while self.stack and self.stack[-1] > x:
            self.stack.pop()
        self.stack.append(x)

    def pop(self):
        return self.stack.pop() if self.stack else None

    def top(self):
        return self.stack[-1] if self.stack else None

    def is_empty(self):
        return len(self.stack) == 0

# Example usage
stack = MonotonicIncreasingStack()
for num in [3, 1, 4, 1, 5, 9, 2, 6]:
    stack.push(num)

print(stack.stack)  # Output: [1, 1, 2, 6]

You can easily modify this implementation to create a monotonic decreasing stack by changing the comparison operator in the push method.

Common Pitfalls and How to Avoid Them

While monotonic stacks are powerful, there are some common pitfalls to watch out for:

  1. Forgetting to handle edge cases: Always consider what happens when the stack is empty or when you reach the end of the input array.
  2. Incorrect monotonicity: Make sure you’re using the correct type of monotonic stack (increasing or decreasing) for your problem.
  3. Not considering duplicates: Some problems may require special handling of duplicate elements. Be sure to clarify how duplicates should be treated in your problem statement.
  4. Overlooking the possibility of using monotonic stacks: Sometimes, the applicability of a monotonic stack isn’t immediately obvious. Train yourself to recognize patterns where monotonic stacks could be useful.

Practice Problems

To solidify your understanding of monotonic stacks, here are some practice problems you can try:

  1. LeetCode 84: Largest Rectangle in Histogram
  2. LeetCode 85: Maximal Rectangle
  3. LeetCode 42: Trapping Rain Water
  4. LeetCode 739: Daily Temperatures
  5. LeetCode 901: Online Stock Span
  6. LeetCode 503: Next Greater Element II
  7. LeetCode 1019: Next Greater Node In Linked List

Conclusion

Monotonic stacks are a powerful tool in the world of algorithmic problem-solving. They excel at handling problems involving “next greater/smaller element” scenarios, histogram calculations, and various other situations where maintaining an ordered stack can provide efficient solutions.

As you prepare for technical interviews, particularly for positions at major tech companies, mastering the use of monotonic stacks can give you a significant advantage. They allow you to solve complex problems with elegant, efficient solutions that showcase your algorithmic thinking skills.

Remember, the key to mastering any algorithmic technique is practice. Try implementing monotonic stacks in various scenarios, solve related problems, and analyze how they can be applied to different types of challenges. With time and experience, you’ll develop an intuition for when a monotonic stack might be the optimal solution to a problem.

As you continue your journey in coding education and programming skills development, keep monotonic stacks in your toolkit. They’re not just useful for solving interview problems, but can also be applied in real-world scenarios where efficient data processing and analysis are required.

Happy coding, and may your stacks always be monotonic when needed!