Problem 261817 · easy · Level 02 Linear Data Structures

Stack With Min and Max

stacks · class design

Design a class BoundsStack: a stack of integers that can also report its smallest and largest element in constant time.

  • BoundsStack(): create an empty stack.
  • push(x): push x.
  • pop(): remove and return the top element.
  • top(): return the top element without removing it.
  • min_val(): return the smallest element currently on the stack.
  • max_val(): return the largest element currently on the stack.

pop, top, min_val and max_val are only called on a non-empty stack.

Examples

Input:  ops  = ["BoundsStack", "push", "push", "push", "min_val", "max_val", "pop", "min_val", "max_val", "top"]
        args = [[], [4], [9], [1], [], [], [], [], [], []]
Output: [None, None, None, None, 1, 9, 1, 4, 9, 9]
Explanation: after pushing 4, 9, 1 the min is 1 and max is 9; popping the 1 makes the min 4 again.

Constraints

  • At most 2 * 10**4 operations
  • Target: O(1) per operation

Goals

  • Store extra bookkeeping alongside each pushed value
  • Answer min and max in O(1) without scanning the stack
Starting Python…