Data structure that deletes all elements of a set less than or equal to x in O(1) time

Question

I am self studying for an algorithms course, and I am trying to solve the following problem:

Describe a data structure to store a set of real numbers, which can perform each of the following operations in O(1) amortized time:

Insert(x) : Deletes all elements not greater than x, and adds x to the set.
FindMin() : Find minimum value of set.

I realize that findmin kind of becomes trivial once you have Insert, and see how with a linked list implementation, you could delete multiple elements simultaneously (ie O(1)), but finding out which link to delete (aka where x goes) seems like an O(n) or O(log n) operation, not O(1). The problem gave the hint: Consider using a stack, but I don't see how this is helpful.

Any help is appreciated.

The original question is below:

Answer 1

Note that your goal is to get O(1) amortized time, not O(1) time. This means that you can do as much work as you'd like per operation as long as n operations don't take more than O(n) time.

Here's a simple solution. Store the elements in a stack in ascending order. To insert an element, keep popping the stack until it's empty or until the top element is greater than x, then push x onto the stack. To do a find-min, read the top of the stack.

Find-min clearly runs in time O(1). Let now look at insert. Intuitively, each element is pushed and popped at most once, so we can spread the work of an expensive insert across cheaper inserts. More formally, let the potential be n, the number of elements on the stack. Each time you do an insert, you'll do some number of pops (say, k) and the potential increases by 1 - k (one new element added, k removed). The amortized cost is then k + 1 + 1 - k, which is 2. Therefore, insert is amortized O(1).

Hope this helps!