Data Structures

Question 1

What is a monotonic stack?

Answer 1

With regards to data structures, monotonic collections contain ordered sets in increasing or decreasing order. With stacks, this means that each element in the stack is in increasing or decreasing order.

Question 2

What conditions do you look for if you want to use a monotone stack?

Answer 2

1) It is a “range queries in an array” problem.
2) The minima/maxima element or the monotonic order of elements in a range is useful to get answer of every range query.
3) When a element is popped from the monotonic stack, it will never be used again.

Question 3

How would you get the next largest number in a list? For example: [4,9,1,3,10]

Answer 3

This is the general way of getting the next largest number in a sequence

def get_next_largest_number(list: List[int]) -> List[int]:    
    length = len(list)

    # We use a monotonic to track largest number seen thus far
    stack = []

    # This collection contains the next largest number for each index. We set this to None to start off with to show that there is no next largest number.
    answer = [None] * length
    curIdx = length - 1
    while (curIdx > -1):
        currentValue = list[curIdx]

    while stack and list[stack[-1]] < currentValue:
        stack.pop()
    answer[curIdx] = stack[-1] if stack else None
    stack.append(curIdx)
    curIdx -= 1
return answer