Stack • Advanced Design

Special Stack (Min Stack)

Design a Data Structure SpecialStack that supports all the stack operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should return minimum element from the SpecialStack. All these operations must be O(1).

The O(N) Space Approach

Use two stacks: one to store actual elements, and another auxiliary stack to store the minimums. When pushing `x`, push it to the main stack. Push `min(x, aux.top())` to the auxiliary stack.

The O(1) Space Approach (Formula)

Store an encoded value when pushing a new minimum. The formula `2 * X - minElement` stores a value strictly less than the new minimum, acting as a flag. Upon popping this flag, you can decode the previous minimum.

Why not sorting?

If you used a sorted array or heap, `getMin()` would be O(1), but `push` and `pop` would become O(log N) or O(N). The Special Stack maintains O(1) across the board by tracking history at every node.

Loading Lab...

Stack • Advanced Design

Special Stack (Min Stack)

The O(N) Space Approach

Use two stacks: one to store actual elements, and another auxiliary stack to store the minimums. When pushing `x`, push it to the main stack. Push `min(x, aux.top())` to the auxiliary stack.

The O(1) Space Approach (Formula)

Why not sorting?

If you used a sorted array or heap, `getMin()` would be O(1), but `push` and `pop` would become O(log N) or O(N). The Special Stack maintains O(1) across the board by tracking history at every node.