Monotonic Stack

#monotonicstack #dsa #algorithms #stack

Prologue

A Monotonic Stack is a data structure that helps solve a class of problems efficiently. It is essentially a stack that maintains a specific ordering property, either increasing or decreasing, for its elements.

To understand a monotonic stack, let's start with a simple stack. A stack is a last-in, first-out (LIFO) data structure, meaning that the element added last is the first one to be removed. It supports two primary operations: push, which adds an element to the top of the stack, and pop, which removes the top element from the stack.

Introduction

In a monotonic stack, elements are stored in such a way that they either form a strictly increasing or decreasing sequence from the bottom to the top of the stack. The ordering property depends on the problem we are trying to solve.

The key characteristic of a monotonic stack is that it allows efficient computation of certain types of information, such as the next greater element, the next smaller element, or the nearest greater or smaller element for each element in a given sequence.

Implementation

To implement a monotonic stack, we usually use a regular stack and add some additional logic. When adding an element to the stack, we compare it with the top element of the stack. If the new element breaks the ordering property, we remove elements from the stack until the ordering property is satisfied again. This ensures that the stack maintains its monotonicity.

Let's consider an example problem to illustrate the usefulness of a monotonic stack. Suppose we have an array of integers, and for each element, we want to find the next greater element to the right. In other words, for each element, we want to find the first element to its right that is larger than it.

We can solve this problem efficiently using a monotonic stack.

We iterate through the array from left to right and perform the following steps for each element:

While the stack is not empty and the current element is greater than the top element of the stack, we know that the current element is the next greater element for the top element.
We store this information and remove the top element from the stack.
Push the current element onto the stack.
At the end of this process, any elements remaining in the stack do not have a greater element to their right.

By following this approach, we can find the next greater element for each element in a single pass through the array, with a time complexity of O(n), where n is the number of elements in the array.

This is just one example of how a monotonic stack can be used.

Depending on the problem, the ordering property and the specific operations performed on the stack may vary. However, the underlying idea remains the same:

using a stack to maintain a monotonic sequence of elements allows for efficient computation of certain information

Problem

Here are a few examples of problems that can be efficiently solved using a monotonic stack:

Next Greater Element: Given an array of integers, find the next greater element for each element in the array. The next greater element is the first element to the right that is larger than the current element.
Next Smaller Element: Similar to the previous problem, but instead, find the next smaller element for each element in the array. The next smaller element is the first element to the right that is smaller than the current element.
Nearest Greater Element: Given an array of integers, find the nearest greater element for each element in the array. The nearest greater element can be either on the left or the right side of the current element.
Nearest Smaller Element: Similar to the previous problem, but instead, find the nearest smaller element for each element in the array. The nearest smaller element can be either on the left or the right side of the current element.
Maximum Area of Histogram: Given an array representing the heights of bars in a histogram, find the maximum possible area of a rectangle that can be formed within the histogram.
Maximum Area of Binary Matrix: Given a binary matrix (matrix with only 0s and 1s), find the largest rectangular sub-matrix that contains only 1s.
Rainwater Trapping: Given an array representing the heights of bars, where each bar represents a wall, calculate the total amount of rainwater that can be trapped between the bars.

These are just a few examples, but there are other problems where a monotonic stack can be used effectively. The key is to identify situations where maintaining a monotonic sequence of elements can help optimize the computation of certain information.

Problems from Leetcode

See full List of Problems

LC#496. Next Greater Element I

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.

You are given 2 distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Brute Force

public int[] nextGreaterElementBruteForce(int[] nums1, int[] nums2) {
    int[] res = new int[nums1.length];
    int k = 0;
    for (int x : nums1) {
      for (int j = 0; j < nums2.length; j++) {
        if (x == nums2[j]) {
          res[k++] = getNextGreater(nums2, j, x);
        }
      }
    }
    return res;
  }

  private int getNextGreater(int nums[], int start, int t) {
    if (start >= nums.length - 1) return -1;

    for (int i = start; i < nums.length; i++) {
      if (nums[i] > t) {
        return nums[i];
      }
    }

    return -1;
  }

TC: O(N^2)
SC: O(1)

Using Stack and Map

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        int k = 0;

        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();

        for (int i=nums2.length-1; i>= 0; i--) {

            int curr = nums2[i];

            while (!stack.isEmpty() && curr > stack.peek()) {
                stack.pop();
            }

            if(stack.isEmpty()){
                map.put(curr, -1);
            }else{
                map.put(curr, stack.peek());
            }

            stack.push(curr);
        }

         for (int i = 0; i < nums1.length; i++){
            res[i] = map.getOrDefault(nums1[i], -1); 
         }


        return res;
    }