Max Stack

Hard · Stack & Monotonic Stack · about 30 minutes

Asked at LinkedIn, Amazon, Meta, Lyft, ByteDance.

Design a stack that also supports finding and removing the maximum element.

  • MaxStack() creates an empty stack.
  • push(x) pushes x; pop() removes and returns the top; top() returns the top.
  • peekMax() returns the maximum element.
  • popMax() removes and returns the maximum element; if several share the maximum, remove the top-most one.

Calls are always valid. Aim for O(log n) per call (O(1) for top).

Related guides