Monotonic Stack

Keeps a stack whose values are always increasing or decreasing. A new element that breaks the order resolves every element it pops — a classic tool for 'next greater/smaller element' style problems, amortized O(n) since each index is pushed and popped once.

Category: Algorithmic Techniques
Time complexity: O(n)
Space complexity: O(n)

Pseudocode

for each i:
  while stack top < a[i]: pop it, record NGE = a[i]
  push i

Reference implementation

stack = []
nge = [-1] * n
for i in range(n):
    while stack and a[stack[-1]] &lt; a[i]:
        nge[stack.pop()] = a[i]
    stack.append(i)

Open the interactive Monotonic Stack visualisation →