Stack With GetMin in O(1)

EasyPython

Problem

UiPath Orchestrator can process sequences of Robot execution events where the most recent event must be removed first. Implement a stack that supports retrieving the smallest stored value without scanning the stack.

Create min_stack(operations), which processes a sequence of operations and returns the results of every operation that produces a value. The stack must support push, pop, top, and getMin, with each operation running in O(1) time.

Formal Specification

operations is a list of operation lists.
push has the form ["push", value], where value is an integer.
pop, top, and getMin have the form ["pop"], ["top"], or ["getMin"].
Return a list containing the result of every pop, top, and getMin, in their original order.
Every pop, top, or getMin operation is valid only when the stack is non-empty.
push does not add an item to the returned result list.

Constraints

1 <= operations.length <= 10^5
-10^9 <= value <= 10^9
Every pop, top, and getMin operation is performed on a non-empty stack
Each operation must run in O(1) time

Function Signature

def min_stack(operations):

Formal Specification

operations is a list of operation lists.
push has the form ["push", value], where value is an integer.
pop, top, and getMin have the form ["pop"], ["top"], or ["getMin"].
Return a list containing the result of every pop, top, and getMin, in their original order.
Every pop, top, or getMin operation is valid only when the stack is non-empty.
push does not add an item to the returned result list.