Make delicious recipes!

Create a stack which supports minimum() in O(1)


If we keep a variable ‘min’ which will be updated each time an element from the stack is pushed or popped, it will work only when element is pushed. During pop, it will be harder to determine the next minimum if the node being popped was the minimum node.


Solution is to have each stack node keep minimum of all nodes below it.

So during each insertion, minimum of new node is just the minimum of stack top and new node.

During deletion, minimum of stack is already there in the next top.


Similarly, a max can be kept in each node along with min to give max/min in O(1)



Optimization


If the stack is very large, then the above approach may be wasting a lot of space.
A better approach may be to have a separate stack just to store the minimums.
This stack will store a decreasing order of nodes (from bottom to top) such that a new node will come on top
only when its smaller than the current minimum on this stack

When adding a new node to stack, this approach will store only the decreasing nodes and not the intermediate higher-valued nodes.
When deleting from the stack, new stack-top is compared with the min-stack's top.
If its larger than the min-stack's top, then the top of min-stack is also removed.






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal