Problem Statement
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class with push, pop, top, and getMin operations.
Approach
Use two stacks: one for values and one for minimum values at each level.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(1) for all operations |
| Space | O(n) |
Examples
Example 1
Input: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()
Output: [null,null,null,-3,null,0,-2]
Explanation: Stack operations
Constraints
- ▸
-2^31 <= val <= 2^31 - 1 - ▸Methods pop, top and getMin will always be called on non-empty stacks
- ▸At most 3 * 10^4 calls
Loading...
Sign in to run your code...
Asked by companies:
AmazonBloombergGoogleMicrosoft