Find the minimum element in a stack in O(1) complexity

Question

Accepted Answer

To find the minimum element in a stack in O(1) complexity, we can use an auxiliary stack.

Create an auxiliary stack to keep track of the minimum element.
Push the first element of the main stack onto the auxiliary stack.
For each subsequent element, compare it with the top element of the auxiliary stack.
If it is smaller, push it onto the auxiliary stack.
To get the minimum element, simply return the top element of the auxiliary stack.
When popping elements from the main stack, also pop the top element of the auxiliary stack if it is the same.
This ensures that the auxiliary stack always contains the minimum element.
This approach has a space complexity of O(n) but a time complexity of O(1).

Popular interview questions of Data Analyst