Monotonic Stack

A monotonic stack is a stack that is always sorted in a monotonic way. The
monotonic stack is a useful data structure for solving problems that require
finding the next greater element or the next smaller element.

Next Greater Element

Given an array of integers, find the next greater element for each element in
the array. The next greater element of an element x is the first greater
element that is to the right of x in the array. If there is no greater
element, then the next greater element is -1.

For example, given the array [2, 5, 3, 7, 4, 9], the next greater element
for each element is [5,7,7,9,9,-1].

Solution

The solution is to use a monotonic stack. The stack will store the indices of
the array. The stack will be sorted in a monotonic decreasing way. The
algorithm is as follows:

1. Create an array nextGreater of the same size as the input array. The
   array will store the next greater element for each element in the input
   array.
2. Create an empty stack.
3. Iterate through the array from left to right.
4. If the stack is empty, push the current index onto the stack.
5. If the stack is not empty, pop the top element from the stack. If the
   element at the popped index is less than the current element, then the
   current element is the next greater element for the element at the popped
   index. Store the current element in the nextGreater array at the popped
   index. Repeat this step until the stack is empty or the element at the
   top of the stack is greater than or equal to the current element.
6. Push the current index onto the stack.
7. Repeat steps 3-6 until the end of the array is reached.
8. While the stack is not empty, pop the top element from the stack. The
   element at the popped index has no next greater element. Store -1 in the
   nextGreater array at the popped index.
9. Return the nextGreater array.

The time complexity of the algorithm is O(n) and the space complexity is
O(n). And vice versa for the next smaller element.

Example Question

Leetcode 907. Sum of Subarray Minimums is a good example question that uses a monotonic stack.

Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.
Since the answer may be large, return the answer modulo 10^9 + 7.

TLE Solution

The naive solution is to iterate through every subarray and find the minimum. Ignoring the constant factors, the time complexity of this solution is O(n^3).

NAIVE Solution Code

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int sum=0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) { 
                //get min of subarray
                sum+= Arrays.stream( Arrays.copyOfRange(arr, i, j + 1)).min().getAsInt();

            }
        }
        return sum;
    }
}

The above solution will get a TLE for large inputs.

Better Solution With Monotonic Stack

The better solution is to use a monotonic stack. The stack will store the indices of the array. The stack will be sorted in a monotonic increasing way. The algorithm is as follows:

Code

class Solution {
    public int sumSubarrayMins(int[] arr) {
        long sum = 0;
        Stack<Integer> stack = new Stack<> ();
        for (int i = 0; i <= arr.length; i++) {
            while (!stack.isEmpty() && (i == arr.length || arr[stack.peek()] > arr[i])) {
                int pop = stack.pop(), prev = stack.isEmpty() ? -1 : stack.peek();
                sum += (pop - prev) * (i - pop) * (long)arr[pop];
            }
            stack.push(i);
        }
        return (int)(sum % (Math.pow(10,9) + 7));
    }
}

The time complexity of the algorithm is O(n) and the space complexity is O(n).

References

• Next Greater Element
• Next Smaller Element
• Monotonic Stack