Last updated on January 19th, 2025 at 10:51 pm

Here, we see a Min Stack LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Design, Stack

Companies

Amazon, Bloomberg, Google, Snapchat, Uber, Zenefits

Level of Question

Medium

Min Stack LeetCode Solution

1. Problem Statement

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.

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

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Monotonic Stack”. This pattern is used to maintain a stack where each element is associated with some additional information (in this case, the minimum value up to that point). This allows efficient retrieval of the minimum value in constant time.

3. Code Implementation in Different Languages

3.1 Min Stack C++

class MinStack {
 public:
  void push(int x) {
    if (stack.empty())
      stack.emplace(x, x);
    else
      stack.emplace(x, min(x, stack.top().second));
  }
  void pop() {
    stack.pop();
  }
  int top() {
    return stack.top().first;
  }
  int getMin() {
    return stack.top().second;
  }
 private:
  stack<pair<int, int>> stack;  // {x, min}
};

3.2 Min Stack Java

class MinStack {
    int min = Integer.MAX_VALUE;
    Stack<Integer> stack = new Stack<Integer>();
    public void push(int x) {
        if(x <= min){          
            stack.push(min);
            min=x;
        }
        stack.push(x);
    }
    public void pop() {
        if(stack.pop() == min) min=stack.pop();
    }
    public int top() {
        return stack.peek();
    }
    public int getMin() {
        return min;
    }
}

3.3 Min Stack JavaScript

var MinStack = function() {
  this.elements = [];
};
MinStack.prototype.push = function(x) {
  this.elements.push({
    value: x,
    min: this.elements.length === 0 ? x : Math.min(x, this.getMin()),
  });
};
MinStack.prototype.pop = function() {
  this.elements.pop();
};
MinStack.prototype.top = function() {
  return this.elements[this.elements.length - 1].value;
};
MinStack.prototype.getMin = function() {
  return this.elements[this.elements.length - 1].min;
};

3.4 Min Stack Python

class MinStack:
    def __init__(self):
        self.stack= []
    def push(self, val):
        if not self.stack:self.stack.append((val,val)) 
        else:
            self.stack.append((val,min(val,self.stack[-1][1])))
    def pop(self):
        if self.stack: self.stack.pop()
    def top(self):
        if self.stack: return self.stack[-1][0]
        else: return None
    def getMin(self):
        if self.stack: return self.stack[-1][1]
        else: return None

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(1)	O(n)
Java	O(1)	O(n)
JavaScript	O(1)	O(n)
Python	O(1)	O(n)

• All implementations follow the same logic but differ slightly in syntax and implementation details.
• The use of a monotonic stack ensures that all operations are efficient, with O(1) time complexity for each operation.
• The space complexity is linear (O(n)) because the stack grows with the number of elements pushed onto it.