155. Min Stack

[sophryu99]

155. Min Stack

https://leetcode.com/problems/min-stack/description/

The insight is to keep track of the minimum value so far and push it, along with the number we are pushing, onto the stack.

1. Push a tuple (number we are pushing, the minimum value so far) to the stack
2. pop and get from a stack has a constant time complexity

class MinStack:

    def __init__(self):
        self.q = []

    def push(self, val: int) -> None:
        if self.q:
            minval = self.q[-1][1]
            if val < minval:
                self.q.append((val, val))
            else:
                self.q.append((val, minval))
        else:
            self.q.append((val, val))

    def pop(self) -> None:
        # O(1)
        self.q.pop()

    def top(self) -> int:
        # O(1)
        return self.q[-1][0]

    def getMin(self) -> int:
        # O(1)
        if len(self.q) == 0:
            return None
        return self.q[-1][1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

n: number of values

• Time Complexity: O(1)
• Space Complexity: O(n) stack