# LeetCode 'Min Stack' Solution

Martin Kysel · June 3, 2024

##### Short Problem Definition:

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.

Min Stack

##### Complexity:

time complexity is `O(1)`

space complexity is `O(N)`

##### Execution:

This one is a head scratcher. It took a bit to figure it out. My brain immediately went to heaps, but they don’t support a `last-inserted` operation. Plus insert is `log(N)`.

After a while I figured out that I can keep a running min and do some code gymnastics to keep it up-to-date.

I’ve seen solutions that have two stacks, one for the `val` and one for `min`. The code is simpler but needs twice the space.

##### Solution:
``````class MinStack:

def __init__(self):
self.stack = []
self.min_val = None

def push(self, val: int) -> None:
if self.min_val == None:
self.min_val = val
self.min_val = min(self.min_val, val)
self.stack.append((val, self.min_val))

def pop(self) -> None:
ret = self.stack.pop()[0]
if len(self.stack) == 0:
self.min_val = None
else:
self.min_val = max(self.min_val, self.stack[-1][1])
return ret

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

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

``````

#### ChatGPT

ChatGPT can solve this problem correctly but does the inefficient two stack solution. I suspect that is the reason why most submissions on LeetCode use two stacks…

``````class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []

def push(self, val: int) -> None:
self.stack.append(val)
# If min_stack is empty or the new value is less than or equal to the current minimum, push it onto min_stack
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)

def pop(self) -> None:
if self.stack:
val = self.stack.pop()
# If the value being popped is the current minimum, pop it from min_stack as well
if val == self.min_stack[-1]:
self.min_stack.pop()

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

def getMin(self) -> int:
if self.min_stack:
return self.min_stack[-1]
return None
``````