Amazon Interview Question: Design a MinStack
Design a stack that supports operations:- 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.
MinStack minStack = new MinStack();
minStack.getMin(); --> Returns -3.
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
Initial takes on the question
The question asks us to create a stack which can support the following operations:
- push: Insert an element into the stack
- pop: Remove an element from the stack
- getMin: Display the smallest element in the current stack.
- getTop: Display the topmost element in the current stack
What do we know?
- A Stack data structure follows the LAST IN FIRST OUT or the LIFO methodology
- By virtue of which, the element that got inserted first is the element that will come out at last!
- A Traditional stack supports the push,pop,peek operations to implement the first three requirements.
- But to attain the minimum element at all times we need to make our own data structure and this is what this challange is all about.
Thinking about keeping a globalMinimum at all times sounds good but in reality, is not useful.
The moment we pop out the globalMinimum from the stack, we will be in no place to tell in Constant time that which is the smallest one.
The idea is to use Two stacks! It might not be all that intuitive but makes a lot of sense when you see how it operates.
At all times we will maintain a parallel extra stack which will account for the minimum element anytime it is asked for.
Let's see how each of these operations will pan out using this idea:
1. Push into the stack:
We make a simple append for the actual stack and the minStack, we will append the minimum minStack's top and the current element.
What this does is that it allows us to keep track of the minimum element at all times!
2. Pop out of stack:
This is a simple pop operation for both actual stack and minStack because we are simply reducing the height of stacks by one level, so we don't need the
minimum value at that level.
Geting the top element in obvious ways corresponds to knowing the actual top element, hence we just use the actual stack and display the top most guy.
Getting the minimm element at any level, is plain simple now that we have our minStack ready all times! Whenever we are asked to tell the current
minimm element, we can easily tell it by looking at the top of the minStack.
Pop opeations are done at places denoted by red arrow in the diagram below and getMin is denoted by green arrow
Now instead of using two stacks, keeping a tuple within a single stack will also create the exact same effect.
Looks a lot more cleaner this way!
The example given at the beginning will make sense now:
Implementation in Python for the minStack class
self.stack = [(-1, float('inf'))]
def push(self, x):
self.stack.append([x, min(x, self.stack[-1])])
if len(self.stack) > 1: self.stack.pop()
if len(self.stack) == 1: return None