# Min Stack See the harder related problem Max Stack.

## # Solution

Note the requirement in the prompt: constant time. So need to come up w/ getMin in time.

### # Stack of val/min Pairs

Since current_min is only the minimum seen below current elt and never above, we could store the value/minimum pair into the stack. Note the not self.stack base case.

Complexity:

• time: for all operations
• space:
class MinStack:

def __init__(self):
"""
"""
self.stack = []

def push(self, x: int) -> None:
# base case
if not self.stack:
self.stack.append([x,x])
return
current_min = self.stack[-1]
self.stack.append([x,min(current_min,x)])

def pop(self) -> None:
self.stack.pop()

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

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


### # Two Stacks

Since the minimums would have many duplicates, we could instead use the self.min_stack to store the minima.

Note that we should also store when x equals current min. Consider this case: self.stack is [2,1,1]. If we don't store the 2nd 1 to self.min_stack, getMin on [2,1] would be 2.

Complexity:

• time: for all operations
• space:
class MinStack:

def __init__(self):
"""
"""
self.stack = []
self.min_stack = []

def push(self, x: int) -> None:
self.stack.append(x)
# should also store when x equals current min
if not self.min_stack or x<=self.min_stack[-1]:
self.min_stack.append(x)

def pop(self) -> None:
if self.stack[-1]==self.min_stack[-1]:
self.min_stack.pop()
self.stack.pop()

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

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


### # Improved Two Stacks

We could further improve the two stacks solution by combining the duplicates into a count.

Note that self.min_stack stores the [minimum, count] pairs.

class MinStack:

def __init__(self):
"""
"""
self.stack = []
self.min_stack = []

def push(self, x: int) -> None:
self.stack.append(x)
if not self.min_stack or x<self.min_stack[-1]:
self.min_stack.append([x,1])
elif x==self.min_stack[-1]:
self.min_stack[-1]+=1

def pop(self) -> None:
if self.stack[-1]==self.min_stack[-1]:
if self.min_stack[-1]>1:
self.min_stack[-1]-=1
else:
self.min_stack.pop()
self.stack.pop()

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

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

Last Updated: 5/13/2020, 7:39:18 AM