Implement a stack that supports these operations in O(1) time each:

Operations

• push(x)
• pop()
• top() -> x
• getMin() -> min

Rules / Constraints:

• pop() and top() should handle empty stack (either throw or return null, but be consistent).
• Duplicates exist.
• Negative values exist.
• Must be O(1) time, O(n) space.

Example

push(5)
push(2)
push(2)
getMin() -> 2
pop()     // pops 2
getMin() -> 2
pop()     // pops 2
getMin() -> 5