Design a stack + findmin and deletemin in O(1)?

Question

I saw this answer to the question about designing a stack with findmin in O(1) time:

https://stackoverflow.com/a/3435998/2653179

What if the request is the same:

Devise a stack-like data structure that does push, pop and min (or max) operations 
in O(1) time. There are no space constraints.

But deletemin also should be in O(1)? Is it possible?

No `deletemin` is not possible in O(1). – n. m. could be an AI Oct 13 '13 at 13:35 — n. m. could be an AI, Oct 13 '13 at 13:35

score 5 · Accepted Answer · answered Oct 13 '13 at 13:38

No. It cannot be done - because it will allow O(n) sorting.

Assume there is such a DS, let it be D
Let A be an input array.
push all elements from A to D.
while D is not empty:
   yield D.min()
   D.popMin()

The above will run in O(n) assuming popMin() and min() are O(1), and will sort an array.
However, sorting is Omega(nlogn) problem. Contradiction.
Thus we can conclude such a DS does not exist,

Design a stack + findmin and deletemin in O(1)?

1 Answers1