Monotonic Stack

Monotonic Stack is a stack where all elements from bottom to top are in increase or decrease other. In a Mono-decrease stack has the smaller element on the top and the greater on the bottom. The reverse is true for a Mono-increase stack.

In the classic game Hanoi Tower, the player needs to move discs from one pin to other without putting a bigger disc on top of a smaller one. The towers are Mono-decrease stacks.

Problem: Next greater integer in unsorted array

Given array \(a\) with \(n\) integers, return an array \(r\) where \(r[i]=j\) is the smallest value such that \(a[j] > a[i]\) and \(j>i\), or \(r[i]=-1\) if there is no such \(j\).

Time complexity: \(O(n)\)
Space complexity: \(O(n)\)

from collections import deque


def next_greater(a):
    ans = [-1] * len(a)
    stack = deque(maxlen=len(a))
    for i, x in enumerate(a):
        while len(stack) > 0 and a[stack[-1]] < x:
            ans[stack[-1]] = i
            stack.pop()
        stack.append(i)
    return ans


assert next_greater([1]) == [-1]
assert next_greater([1, 2, 3]) == [1, 2, -1]
assert next_greater([1, 3, 2]) == [1, -1, -1]
assert next_greater([3, 2, 1]) == [-1, -1, -1]
assert next_greater([3, 1, 2]) == [-1, 2, -1]

Problem: Next smaller in unsorted array

Given array \(a\) with \(n\) integers, return an array \(r\) where \(r[i]=j\) is the smallest value such that \(a[j] < a[i]\) and \(j>i\), or \(r[i]=-1\) if there is no such \(j\).

Time complexity: \(O(n)\)
Space complexity: \(O(n)\)

from collections import deque


def next_smaller(a):
      ans = [-1] * len(a)
      stack = deque(maxlen=len(a))
      for i, x in enumerate(a):
            while len(stack) > 0 and a[stack[-1]] > x:
                  ans[stack[-1]] = i
                  stack.pop()
            stack.append(i)
      return ans


assert next_smaller([1]) == [-1]
assert next_smaller([1, 2, 3]) == [-1, -1, -1]
assert next_smaller([1, 3, 2]) == [-1,  2, -1]
assert next_smaller([3, 2, 1]) == [ 1,  2, -1]
assert next_smaller([3, 1, 2]) == [ 1, -1, -1]

Problem: Previous greater integer in unsorted array

Given array \(a\) with \(n\) integers, return an array \(r\) where \(r[i]=j\) is the greatest value such that \(a[j] > a[i]\) and \(j

Time complexity: \(O(n)\)
Space complexity: \(O(n)\)

from collections import deque


def prev_greater(a):
    ans = [-1] * len(a)
    stack = deque(maxlen=len(a))
    for i, x in enumerate(a):
        while len(stack) > 0 and a[stack[-1]] < x:
            stack.pop()
        ans[i] = -1 if len(stack) == 0 else stack[-1]
        stack.append(i)
    return ans


assert prev_greater([1]) == [-1]
assert prev_greater([1, 2, 3]) == [-1, -1, -1]
assert prev_greater([1, 3, 2]) == [-1, -1,  1]
assert prev_greater([3, 2, 1]) == [-1,  0,  1]
assert prev_greater([3, 1, 2]) == [-1,  0,  0]

Problem: Previous smaller integer in unsorted array

Given array \(a\) with \(n\) integers, return an array \(r\) where \(r[i]=j\) is the greatest value such that \(a[j] < a[i]\) and \(j

Time complexity: \(O(n)\)
Space complexity: \(O(n)\)

from collections import deque


def prev_smaller(a):
    ans = [-1] * len(a)
    stack = deque(maxlen=len(a))
    for i, x in enumerate(a):
        while len(stack) > 0 and a[stack[-1]] > x:
            stack.pop()
        ans[i] = -1 if len(stack) == 0 else stack[-1]
        stack.append(i)
    return ans


assert prev_smaller([1]) == [-1]
assert prev_smaller([1, 2, 3]) == [-1,  0,  1]
assert prev_smaller([1, 3, 2]) == [-1,  0,  0]
assert prev_smaller([3, 2, 1]) == [-1, -1, -1]
assert prev_smaller([3, 1, 2]) == [-1, -1,  1]

Problem: Next smallest greater or equal integer in unsorted array

Given array \(a\) with \(n\) integers, return an array \(r\) where \(r[i]=j\) where \(a[j] \geq a[i]\), \(j>i\), \(a[j]\) is the smallest possible value, and \(j\) is the smallest possible value, or \(r[i]=-1\) if there is no such \(j\).

Time complexity: \(O(n \log n)\)
Space complexity: \(O(n)\)

from collections import deque


def next_smallest_greater_or_equal(a):
      n = len(a)
      ans = [-1] * n
      stack = deque(maxlen=n)
      for _, i in sorted(zip(a, range(n))):
            while len(stack) > 0 and stack[-1] < i:
                  ans[stack[-1]] = i
                  stack.pop()
            stack.append(i)
      return ans


assert next_smallest_greater_or_equal([1]) == [-1]
assert next_smallest_greater_or_equal([1, 2, 3]) == [ 1,  2, -1]
assert next_smallest_greater_or_equal([1, 3, 2]) == [ 2, -1, -1]
assert next_smallest_greater_or_equal([3, 2, 1]) == [-1, -1, -1]
assert next_smallest_greater_or_equal([3, 1, 2]) == [-1,  2, -1]

Problem: Next greatest smaller or equal integer in unsorted array

Given array \(a\) with \(n\) integers, return an array \(r\) where \(r[i]=j\) where \(a[j] \leq a[i]\), \(j>i\), \(a[j]\) is the largest possible value, and \(j\) is the smallest possible value, or \(r[i]=-1\) if there is no such \(j\).

Time complexity: \(O(n \log n)\)
Space complexity: \(O(n)\)

from collections import deque


def next_greatest_smaller_or_equal(a):
      n = len(a)
      ans = [-1] * n
      stack = deque(maxlen=n)
      for _, i in sorted(zip(map(lambda v: -v, a), range(n))):
            while len(stack) > 0 and stack[-1] < i:
                  ans[stack[-1]] = i
                  stack.pop()
            stack.append(i)
      return ans


assert next_greatest_smaller_or_equal([1]) == [-1]
assert next_greatest_smaller_or_equal([1, 2, 3]) == [-1, -1, -1]
assert next_greatest_smaller_or_equal([1, 3, 2]) == [-1,  2, -1]
assert next_greatest_smaller_or_equal([3, 2, 1]) == [ 1,  2, -1]
assert next_greatest_smaller_or_equal([3, 1, 2]) == [ 2, -1, -1]

References

Monotonic Stack by Richard Liu