Implement Min Stack

Back to home

𝑻𝒂𝒃𝒍𝒆 𝒐𝒇 𝑪𝒐𝒏𝒕𝒆𝒏𝒕

Problem Statement: Implement Min Stack
Solution with Stack

Logicmojo - Updated Aug 28, 2021

Problem Statement: Implement Min Stack

Implement a stack that supports the following operations in O(1) time complexity:

push(x) : Push the element x onto the stack.

pop() : Removes the element at the top of the stack.

top() : Get the topmost element of the stack.

getMin() : Get the minimum element in the stack.

Assume that pop, top and getMin will only be called on non-empty stack.

Solution:

Internally we maintain a stack of tuples, where the first value represents the value added to the stack, and the second represents the minimum value in the stack at the point of insertion.

Because push and pop operations only occur at the top of the stack, we know that the things elements below the top element won't change. This means that we can know the minimum at any given point by just comparing the top most value with the one immediately before it.

C++ Implementation:

class MinStack {
  stack < pair < int, int >> st;

  public:
    void push(int x) {
      int min;
      if (st.empty()) {
        min = x;
      } else {
        min = std::min(st.top().second, x);
      }
      st.push({x,min});
    }

  void pop() {
    st.pop();
  }

  int top() {
    return st.top().first;
  }

  int getMin() {
    return st.top().second;
  }
};

Python Implementation:

class MinStack:

    def __init__(self):
        self.stack = [] # The stack contains a tuple of the value, 
#and the minimum value at the point that value was added to the stack.
        
    def push(self, x: int) -> None:
        if not self.stack:
            self.stack.append((x, x))
        else:
            currentMin = self.stack[-1][1]
            
            self.stack.append((x, min(x, currentMin)))
        
    def pop(self) -> None:
        return self.stack.pop()[0]
        
    def top(self) -> int:
        return self.stack[-1][0]
        
    def get_min(self) -> int:
        return self.stack[-1][1]
if __name__=='__main__':
    stack = MinStack()
    stack.push(3)
    stack.push(5)
    print('Minimum Value:', stack.get_min())
    stack.push(4)
    stack.push(1)
    print('Minimum Value:', stack.get_min())
    print(stack.pop())
    print('Minimum Value:', stack.get_min())
    print(stack.pop())

Time Complexity: O(1)

Auxiliary Space: O(N)

With this article at Logicmojo, you must have the complete idea of solving Implement Min Stack problem.