Monotonic Data Structures

Stacks are quite simple data structures with LIFO (Last In First Out) property. I added this post with the implementation of a stack using list/slice in python and go.

More constraint properties can be added to this simple stack structure, which can help solve multiple other problems.

In this post I will be talking about stack with monotonic property.

Monotone means same or unchanging. Defining stacks with monotonic increasing/decreasing properties means all elements in the stack are unchangingly increasing or decreasing in nature.

Example of monotonic decreasing stack would be:

st = [20, 15, 10, 5]
# Next valid element should be < 5 to keep the constraint.

An interesting property about such stacks are that it gives the next closest greater/smaller number/index or previous closest greater/smaller number/index for array elements with single iteration over the array.

next closest greater means for any element at index i give nums[j] where nums[j] > nums[i] and j is min(i + 1, n - 1). Similarly previous closest greater means for any element at index i give nums[i] where nums[i] > nums[j] and j is max(0, i - 1).

In an example array: [1, 3, 2, 5, 4, 8, 9, 7] next closest greater values will be [3, 5, 5, 8, 8, 9, -1, -1]. It is important to see for 5 at index 4 although next greater value is 7 at index 7 but the closet greater value is 8 at index 6.

Another inteesting property about such stacks is that maximum number in case of decreasing monotonic stack lies at the bottom of the stack i.e. at index 0 and then second maximum and so on. Similar is the case for finding minimum element in increasing monotonic stack.

Some example problems:

  1. Next greater element I
  2. Next greater element II

In such problems monotonic increasing/decreasing stack can be made, by following three steps.

  • Iterate over each element of the array.
  • If the stack is not empty, pop() all the elements on top of the stack which will violate the monotonic invariant of the stack, once current element is inserted on top of the stack.
  • Insert the current element on top of the stack.

Code to do create a monotonic decreasing stack from nums: List[int].

st = []
for i in range(len(nums)):
    while st and nums[st[-1]] < nums[i]: # For monotonic increasing less than operator changes to greater than.
        # pop all the elements smaller than i for the stack, to be still be monotonic decreasing once i is inserted.
        elem = st.pop()
        #TODO 1 work with elem and i
    #TODO 2 work with i and st[-1] if len(st) > 0
    st.append(i)

In this basic construct the two TODO in code can be used to find next closest greater and previous closest greater element of array elements.

  • TODO 1, gives the next closest greater value for index elem as index i. As if nums[i] was smaller than nums[elem], elem would have not been popped. Value of index i can be stored for index elem in another array or map based on the question.
  • TODO 2, gives the previous greater or equal for index i as value on top of stack i.e. nums[st[-1]]. As if there was any value smaller than nums[i], it would have been popped before reaching TODO 2.

Based on the question next closest greater or previous closest greater index can also be calculated with a trivial change.

Similarly using increasing monotonic stack next closest smaller and previous closest smaller value can be calculated from TODO 1 and TODO 2.

Now let’s look at problem Daily Temperatures

The problem is defined as

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

The problem is asking to find at each ith element the next element j such that temperature[j] > temperature[i] and return j - i for the ith element if j exist else 0.

So based on the blog, it can be seen that the problem is asking to find the next closest greater element index and use that to find the result. So for this decreasing monotonic stack can be used as described above and populate TODO #1 to find the result.

def dailyTemperatures(self, temp: List[int]) -> List[int]:
    st = []
    ans = [0] * len(temp)
    for i in range(len(temp)):
        while st and temp[st[-1]] < temp[i]: # For monotonic increasing less than operator changes to greater than.
            # pop all the elements smaller than i for the stack, to be still be monotonic decreasing once i is inserted.
            elem = st.pop()
            # Update TODO 1 to take difference between i and elem, to find number of elements between next closest greater element.
            ans[elem] = i - elem
        st.append(i)
    return ans

Using a stack here, reduced the time complexity of such problems from O(N^2) to O(N) using extra O(N) space. It is a really good example of optimizing runtime complexity using extra space in such problems.

A good excercise, is to iterate from the end of array, and see what value these stack gives at two TODO lines.

  • Monotonic Queues

An extension of a monotonic stacks are monotonic queues. Such queues still has the elements in increasing or decreasing order but the elements can also be removed from the left end of the queue.

comments powered by Disqus