Stack Implementation in Python

Photo by Debby Hudson on Unsplash

Problem:

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

• push(x) — Push element x onto stack.
• pop() — Removes the element on top of the stack.
• top() — Get the top element.
• getMin() — Retrieve the minimum element in the stack.

Solution:

We can implement the stack using a Python list and use an additional variable to keep track of the minimum element. Every time we push a new element onto the stack, we check if it is the new minimum and update the minimum element if necessary. When we pop an element, we also check if it is the minimum element and update the minimum element if necessary.

Here is the solution code:

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

    def push(self, x: int) -> None:
        if x <= self.min_element:
            self.stack.append(self.min_element)
            self.min_element = x
        self.stack.append(x)

    def pop(self) -> None:
        if self.stack.pop() == self.min_element:
            self.min_element = self.stack.pop()

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

    def getMin(self) -> int:
        return self.min_element

This implementation has a time complexity of O(1) for all of the stack operations.

Here is a step-by-step breakdown of the solution:

1. First, we define a MinStack class that has four methods: push, pop, top, and getMin. We also define two instance variables: stack, which is a list that will be used to store the elements in the stack, and min_element, which will be used to track the minimum element in the stack.

In the __init__ method, we initialize the stack and min_element variables. We set min_element to a very large value (float('inf')) initially, since we have not yet pushed any elements onto the stack.

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

2. In the push method, we first check if the element being pushed (x) is less than or equal to the current minimum element. If it is, we push the current minimum element onto the stack and update the minimum element to be x. This is necessary because when we pop x off the stack later, we will need to know what the previous minimum element was so that we can restore it.

After updating the minimum element if necessary, we push the element x onto the stack.

def push(self, x: int) -> None:
        if x <= self.min_element:
            self.stack.append(self.min_element)
            self.min_element = x
        self.stack.append(x)

3. In the pop method, we first pop the top element off the stack. Then, we check if the element we popped was the minimum element. If it was, we pop another element off the stack (which will be the previous minimum element that we pushed onto the stack in step 3) and update the minimum element to be this value.

def pop(self) -> None:
        if self.stack.pop() == self.min_element:
            self.min_element = self.stack.pop()

4. In the top method, we simply return the top element of the stack.

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

5. In the getMin method, we return the current minimum element.

def getMin(self) -> int:
        return self.min_element

I hope this helps! Let me know if you have any questions about the solution.