# Min Stack

DesignStack

See the harder related problem Max Stack.

## # Driver Code

obj = MinStack()
obj.push(val)
obj.pop()
param_3 = obj.top()
param_4 = obj.getMin()

1
2
3
4
5

## # Solution

Note the requirement in the prompt: constant time. So need to come up w/ getMin in $O(1)$ time.

Complexity

time: $O(1)$ for all operations
space: $O(n)$

### # Stack of val $\rightarrow$ 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.

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][1]
self.stack.append([x,min(current_min,x)])

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

### # 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.

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]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

### # 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][0]:
self.min_stack.append([x,1])
elif x == self.min_stack[-1][0]:
self.min_stack[-1][1]+=1

def pop(self) -> None:
if self.stack[-1]==self.min_stack[-1][0]:
if self.min_stack[-1][1]>1:
self.min_stack[-1][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][0]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25