Min Stack

Medium·Tagsstackdesign

Problem Statement

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. To allow our automated runner to test your class, write a function `runMinStack` that takes an array of operations (`"push"`, `"pop"`, `"top"`, `"getMin"`) and an array of integer arguments for those operations. It should return an array of results for the `top` and `getMin` operations.

Examples

Example 1

Input

ops: ["push", "push", "push", "getMin", "pop", "top", "getMin"], args: [[-2], [0], [-3], [], [], [], []]

Output

"[-3, 0, -2]"

Why

MinStack pushes -2, 0, -3. getMin() returns -3. pop() removes -3. top() returns 0. getMin() returns -2.

Constraints

•1 <= ops.length <= 1000
•Operations will always be valid (no pops on empty stacks).

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

A standard stack only keeps track of the top element. To get the minimum in O(1) time, you need to store more information.

Hint 2

Consider using an auxiliary stack (a second stack) that strictly keeps track of the minimum value at each level of the main stack.