Problem
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x)– Push element x onto stack.pop()– Removes the element on top of the stack.top()– Get the top element.getMin()– Retrieve the minimum element in the stack.
Some questions to ask
- Does this data structure need to be thread-safe?
- What types of elements does it support?
- What to return when calling
getMinortoporpopfor an empty stack?
Approach
class MinStack:
def __init__(self):
# Keep track of current min in separate stack.
self._data = []
self._min = []
def push(self, x: int) -> None:
"""Push element 'x' onto stack."""
self._data.append(x)
# Update current min by comparing 'x' with previous min.
# If stack was empty, then current min is 'x'.
currMin = min(self._min[-1], x) if self._min else x
self._min.append(currMin)
def pop(self) -> None:
"""Removes the element on top of the stack."""
# Sync state of 'data' stack and 'min' stack.
self._data.pop()
self._min.pop()
def top(self) -> int:
"""Get the top element."""
return self._data[-1]
def getMin(self) -> int:
"""Retrive the minimum element in the stack."""
return self._min[-1]
Complexity
All operations run in constant time, but the _min stack does takes up additional space compared to a normal stack.
Other approaches
A naive approach would be to just store the data in a normal stack and find the minimum on demand.
This would take up less space, but getMin() will run in at least
linear time.