159. Min Stack - Support getMin in O(1)

Simulate a stack given n operations, each 'PUSH x', 'POP', or 'GETMIN'. POP silently removes the top element (no output). On GETMIN, print the current minimum value in the stack (or 'EMPTY' if the stack is empty), in O(1) time. Print one result per line, in the order GETMIN operations occurred.

Input: The first line contains an integer n, the number of operations. Each of the next n lines contains one operation: 'PUSH x', 'POP', or 'GETMIN'. Output: Print one line per GETMIN operation, in order, printing the current minimum value or 'EMPTY' if the stack is empty.

1 <= n <= 10^5

This 'maintain a running answer alongside each stack level' technique (tracking min here) generalizes to tracking ANY running aggregate (max, sum, etc.) alongside a stack in O(1) per operation - a broadly reusable pattern.

Build a stack that can report its current minimum value instantly (O(1)), even as elements are pushed and popped. Brute force: On every GETMIN call, scan the entire stack to find its current minimum directly - this costs O(n) per query, too slow if there are many GETMIN calls interspersed with pushes/pops. Optimised: Maintaining a PARALLEL stack that tracks 'the minimum as of this push' means popping the main stack automatically 'reveals' the correct previous minimum on the tracking stack too, with zero rescanning ever needed - both push and GETMIN become O(1).

Maintain the stack normally for PUSH and POP. Whenever a GETMIN query arrives, scan every element currently in the stack to find the smallest one (or report EMPTY if the stack has no elements) and print it. This is correct and needs no extra bookkeeping on PUSH/POP, but every GETMIN query costs time proportional to how many elements are currently on the stack, which the problem explicitly requires to be O(1). Time: O(n) per GETMIN Space: O(1) extra

Keep a second stack alongside the main one that tracks the running minimum: whenever a value x is pushed onto the main stack, also push min(x, current top of the auxiliary stack) (or just x if the auxiliary stack is empty) onto the auxiliary stack; whenever the main stack is popped, pop the auxiliary stack too. GETMIN then just peeks the top of the auxiliary stack in constant time. This achieves the required O(1) per operation, at the cost of an entire second stack of extra memory proportional to the number of elements. Time: O(1) per operation Space: O(n) extra

Track the current minimum in a single variable (not a whole second stack). When pushing x: if x is not smaller than the current minimum, push x as-is; if x is smaller, push an encoded 'marker' value (such as 2*x - currentMin) instead and update currentMin to x. When popping: if the popped value is less than currentMin, it was an encoded marker, so the real previous minimum can be recovered as 2*currentMin - poppedValue, and currentMin is restored to that; otherwise the popped value needed no special handling. GETMIN simply returns currentMin. This achieves the same O(1) time per operation as the two-stack approach, but without ever allocating a second stack, cutting the extra space down to a single tracked variable. Time: O(1) per operation Space: O(1) extra

1. Maintain a SECOND stack that tracks the running minimum AT THE TIME each corresponding element was pushed. 2. On a push, compute the new minimum as the smaller of the new value and the current minimum, and push THAT onto the min-tracking stack (alongside the actual value on the main stack). 3. On a pop, pop from BOTH stacks together - the min-tracking stack's new top automatically reflects the correct minimum for what remains.

Time: O(1) for every operation - push, pop, and getMin. Space: O(n), for the second (parallel minimum-tracking) stack, doubling the space compared to a plain stack.

a GETMIN on an empty stack (print 'EMPTY'); popping the current minimum and confirming the previous minimum resurfaces, as in the example where the minimum reverts from 2 to 3 after a POP; n = 10^5 for performance.

Be ready to mention the SPACE-optimized variant (storing just the DIFFERENCE between the pushed value and the current minimum, rather than a full parallel stack) as a way to reduce the extra space, at the cost of trickier arithmetic - a nice advanced follow-up.