Design a Max Stack

Problem Statement

Design a stack that supports the following operations, ideally all in O(1) time:

1. push(x) — Push element x onto the stack
2. pop() — Remove and return the top element
3. top() — Return the top element without removing it
4. getMax() — Return the maximum element currently in the stack

(This is the "max stack" without the popMax operation.)

Constraints

• All operations should aim for O(1) time
• -10^7 <= x <= 10^7
• At most 10^5 operations
• pop, top, getMax won't be called on an empty stack

Example

push(5)   → stack: [5]           getMax() → 5
push(1)   → stack: [5,1]         getMax() → 5
push(8)   → stack: [5,1,8]       getMax() → 8
pop()     → returns 8            getMax() → 5
top()     → returns 1

What the Interviewer Expects

1. Linear approach first — track max by scanning on every getMax (O(n)). Acknowledge it's suboptimal.
2. Optimal: auxiliary max stack — maintain a second stack that tracks the max at each level.
   • On push: push max(x, currentMax) onto the max stack
   • On pop: pop from both stacks
   • getMax: return top of the max stack (O(1))
3. Space trade-off — O(n) extra space for O(1) getMax. Discuss this trade-off.
4. Dry run — walk through push/pop showing both stacks staying in sync.

Follow-ups

1. How would you add a popMax() operation (remove the maximum element)? What's the complexity now?
2. Can you do it with a single stack storing pairs (value, maxSoFar)?
3. What if you also needed getMin() simultaneously?
4. How would you make it thread-safe for concurrent access?