Min Stack

Simulate a stack that supports retrieving the current minimum in constant time.

You are given two parallel arrays operations and values. At index i:

• if operations[i] == "push", push values[i] onto the stack;
• if operations[i] == "pop", remove the current top element;
• if operations[i] == "top", append the current top element to the answer;
• if operations[i] == "getMin", append the current minimum element to the answer.

values[i] is ignored for pop, top, and getMin operations. The input is always valid: every queried or popped stack is non-empty.

Input / output

• Input: operations: string[], values: int[]
• Output: int[] containing every top and getMin result in order

Examples

1. operations = ["push","push","push","getMin","pop","top","getMin"], values = [-2,0,-3,0,0,0,0] returns [-3,0,-2]. The minimum drops to -3, then returns to -2 after that value is popped.
2. operations = ["push","push","getMin","push","top"], values = [5,1,0,1,0] returns [1,1]. The duplicated minimum should still be tracked correctly.
3. operations = ["push","top","getMin"], values = [7,0,0] returns [7,7]. A one-element stack has the same top and minimum.

Constraints

• 1 <= operations.length == values.length <= 3 * 10^4
• operations[i] is one of "push", "pop", "top", "getMin"
• -10^5 <= values[i] <= 10^5
• All pop, top, and getMin operations are valid

Edge cases

• The minimum can appear multiple times.
• Negative numbers are allowed.
• The stack can shrink back to one element after many operations.

Target complexity

• Aim for O(1) time per operation.
• Aim for O(n) additional space in the worst case.

Hints

1. A plain stack gives push, pop, and top, but not the current minimum fast enough.
2. Store a second stack where each position remembers the minimum value seen up to that depth.

Follow-up How would you redesign this if the stack also needed getMax() in constant time?