We use a native Python stack (list) to implement the pop,push and top

operations. They all achieve the expected O(1), and space is O(n).

For the getMin operation, we use an additional array that will keep track of

the minimum up to certain position i-th; that is

minpos[i] = min(arr[:i])

This second array (stack) can be updated in O(1) as well, because

minpos[i+1] = min(arr[i+1], minpos[i])

hence, we use above formulate inside push implementation. When popping,

we just need to pop from both stacks simultaneously; such that the last

position of minpos will always give global minimum.

So we are able to maintain the complexities of a single stack, even after

considering the extra costs of this minpos.

```
class MinStack:
def __init__(self):
self.stack = []
self.minpos = []
def push(self, x):
self.stack.append(x)
prev = self.minpos[-1] if self.minpos else x
self.minpos.append(min(prev, x))
def pop(self):
self.stack.pop()
self.minpos.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.minpos[-1]
```