Question

In today's Lab we will explore ways to design a Stack with O(1) lookup time of the Minimum element.

You will solve the problem as stated below:
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class:
MinStack initializes the stack object.
- push(int val) pushes the element val onto the stack.
- pop() removes the element on the top of the stack.
- top() gets the top element of the stack.
- getMin() retrieves the minimum element in the stack.

Answer 1

To design a stack with O(1) lookup time for the minimum element, you can use an additional stack called 'minStack'.

Step-by-step explanation:

To design a stack with O(1) lookup time for the minimum element, we can use an additional stack to keep track of the minimum element. We will call this stack the 'minStack.' Here is an implementation of the MinStack class:

1. Create two stacks: 'stack' and 'minStack.'
2. When pushing an element 'val' onto the stack, push 'val' onto the 'stack' and check if 'val' is smaller than or equal to the current minimum element in 'minStack.' If it is, push 'val' onto 'minStack' as well.
3. When popping an element from the stack, pop it from 'stack' and check if the popped element is equal to the top element of 'minStack.' If it is, pop the top element from 'minStack' as well.
4. When getting the top element of the stack, simply return the top element of 'stack.'
5. When retrieving the minimum element, return the top element of 'minStack.'