Monotonic Stack & Queue Patterns

  • Keep indices in sorted order
  • Each index pushed and popped once
  • O(n) total time
1 / 4

Next greater element

  • Decreasing stack of indices
  • Pop while current is larger
  • Popped index found its answer
2 / 4

Histogram max rectangle

  • Increasing stack of heights
  • Pop when height drops
  • Width from previous smaller to current
3 / 4

Monotonic deque

  • Pop back while smaller
  • Pop front if out of window
  • Front is max
4 / 4
Use arrow keys or click edges to navigate. Press H to toggle help, F for fullscreen.