CODEWITHSUNDEEP
data-structuresstackamortized-analysis
Nezo
Nezo

Reputation: 597

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

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:

Original Problem

Upvotes: 4

Views: 855

Answers (2)

Timothy Shields
Timothy Shields

Reputation: 79461

double is the data structure! In the methods below, ds represents the data structure that the operation is being performed on.

void Insert(ref double ds, double x)
{
    ds = x;
}

double FindMin(double ds)
{
    return ds;
}

The only way to ever observe the state of the data structure is to query its minimum element (FindMin). The only way to modify the state of the data structure is to set its new minimum element (Insert). So the data structure is simply the minimum element of the set.

Upvotes: 2

templatetypedef
templatetypedef

Reputation: 372814

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!

Upvotes: 6

Related Questions