Min Stack

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element — all in O(1).

Requirements

• All four operations run in O(1) time.
• pop, top, and getMin are only called when the stack is non-empty — focus on the design, not empty-stack validation.
• getMin returns the minimum of the elements currently on the stack (it must track minima as elements are popped).

API to implement

Implement the class MinStack. The I/O driver is already written in the starter code — it parses the command script below and calls your methods. You only implement the class.

| Command | Returns | Behavior | |---|---|---| | push <val> | — | Push val onto the stack. | | pop | — | Remove the top element. Never called on an empty stack. | | top | int | Return the top element. Never called on an empty stack. | | getMin | int | Return the minimum element currently in the stack, in O(1). Never called on an empty stack. |

Input format

The first line contains Q, the number of operations. Each of the next Q lines is one command as listed above. String arguments contain no spaces.

Output format

For each command with a non-void return, print its result on its own line, in order. The driver does this for you — your methods just return values.

This is a design problem: the hidden tests exercise edge cases and interaction sequences, not performance tricks. Model the state cleanly and the tests will pass.

10
push 5
push 2
getMin
push 7
top
getMin
pop
getMin
pop
getMin

2
7
2
2
5

6
push 3
push 3
getMin
pop
getMin
top

3
3
3