A stack must support push, pop and getMin in O(1) time using O(1) extra space beyond the values themselves, with 64-bit integer entries. Give a construction and state the exact condition on the input range under which it is safe.

A stack must support push, pop and getMin in O(1) time using O(1) extra space beyond the values themselves, with 64-bit integer entries. Give a construction and state the exact condition on the input range under which it is safe.

Approach: The straightforward answer stores a second minimum per element. To drop that, store an encoded value when a new minimum arrives so the previous minimum can be recovered on pop.

Push 2x - min when x is a new minimum and push x otherwise, keeping min in a single variable. On push, if x < min then push the encoded value 2x - min and set min = x, otherwise push x unchanged. On pop, an entry below the current min must be an encoded one, so report min as the value popped and restore min to 2*min - entry. Every operation is a fixed number of arithmetic steps, so all three are O(1), and only one extra machine word is used rather than the auxiliary stack of minima that the standard min stack keeps. The safety condition is that 2x - min must not overflow, which for two's complement 64-bit values means the inputs must lie inside roughly half the representable range, and the extreme case of x = -B pushed against min = +B encodes as -3B, so the exact requirement is 3B <= 2^63: a bound of 2^61 satisfies it and 2^62 does not. Outside that range the encoding wraps silently and getMin returns nonsense, so on unvalidated input the auxiliary stack version is the correct choice.

Follow-up: How do you support getMin over a queue rather than a stack in O(1) amortised, and what changes?

Key concepts: min stack, encoding trick, overflow, auxiliary stack.