155-MinStack

Min Stack

Medium

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]

Explanation MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2

Constraints:

• $-2^{31}$ <= val <= $2^{31} - 1$
• Methods pop, top and getMin operations will always be called on non-empty stacks.
• At most $3 * 10^4$ calls will be made to push, pop, top, and getMin.

Problem can be found in here!

Solution

Solution

class MinStack:
    def __init__(self):
        self.stack = [float("inf")]

    def push(self, val: int) -> None:
        min_value = self.stack[-1]
        self.stack.append(val)
        self.stack.append(min(min_value, val))

    def pop(self) -> None:
        self.stack.pop()
        self.stack.pop()

    def top(self) -> int:
        min_value = self.stack.pop()
        current_value = self.stack.pop()
        self.stack.append(current_value)
        self.stack.append(min_value)
        return current_value

    def getMin(self) -> int:
        return self.stack[-1]

Time Complexity: $O(1)$, Space Complexity: $O(1)$