Stack with Constant-Time Minimum over a Sequence of Operations

Design a stack that supports pushing an element, popping the top element, reading the top element, and reading the smallest element currently in the stack, with every one of these operations taking constant time. To make the design testable as a single function, process a sequence of operations on an initially empty stack and return the values that the reading operations produce.

Function Signature

def run_min_stack(ops: list[str], args: list[int]) -> list[int]:

Rules

• ops[i] is one of "push", "pop", "top", "get_min".
• "push" pushes args[i]. For every other operation, args[i] is 0 and is ignored.
• "pop" removes the top element and produces no output.
• "top" outputs the top element; "get_min" outputs the smallest element currently in the stack. Neither removes anything.
• The stack can hold equal values; each push is a separate element.
• Return the outputs of "top" and "get_min" in the order the operations occur. If there are none, return an empty list.
• Each operation must run in O(1) time; the tests include long sequences on which scanning the stack for every "get_min" is too slow.

Constraints

• 1 <= len(ops) = len(args) <= 10^5
• for "push", -2^31 <= args[i] <= 2^31 - 1, the full signed 32-bit range
• "pop", "top" and "get_min" are only issued when the stack is non-empty

Examples

Example 1

Input: ops = ["push", "push", "push", "get_min", "pop", "top", "get_min"]
 args = [-2, 0, -3, 0, 0, 0, 0]
Output: [-3, 0, -2]

After the three pushes the stack is [-2, 0, -3] (top last) and its minimum is -3. Popping removes -3; the top is then 0 and the minimum is -2.

Example 2

Input: ops = ["push", "push", "push", "get_min", "pop", "get_min", "pop", "get_min"]
 args = [2, 1, 1, 0, 0, 0, 0, 0]
Output: [1, 1, 2]

Two copies of the minimum 1 are pushed. After one is popped the minimum is still 1; after the second is popped it becomes 2.