Algorithm, Part I — Successor with delete

Q: Successor with delete. Given a set of N integers S={0,1,…,N−1} and a sequence of requests of the following form:

  • Remove x from S
  • Find the successor of x: the smallest y in S such that y≥x.

design a data type so that all operations (except construction) should take logarithmic time or better.

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

Well, I have experienced some frustration on this one. Since it is under the context of Union-Find, it is very likely that we need to use Union-Find algorithm. Unfortunately, I didn’t figure out how to apply Union-Find. One step back, if there was no context at all, I probably would not think of using Union-Find at all…But we know now…Again, this suggests that we should practice more problems as the knowledge base, otherwise we won’t have any previous experience to connect with when facing a new problem.

This problem uses a similar approach as the previous post in solving the maximum object in the component. To fit in the union-find frame, the remove operation acts like union, well, with what? The answer is, if we remove x at index i in an array, it is the same as union (array[i], array[i+1]) (except for the last element). And the successor of x would be the largest object in the component which x is a member of. Just try this yourself.

I still can’t figure out how to relate this problem and union-find in the first place. This is the real challenge. If someone has an intuitive idea of how this works, please, leave a comment and share your brilliant idea 🙂

Code  on github:

 

Enhanced by Zemanta
Advertisements
Algorithm, Part I — Successor with delete

5 thoughts on “Algorithm, Part I — Successor with delete

  1. Saurabh says:

    How would you take care of the situation where delete is called on an element which doesn’t exist i.e. it has been deleted before?

  2. Roman says:

    If someone still needs it:

    public class SuccessorRemove {
    private WeightedUF uf;

    public SuccessorRemove(int N) {
    uf = new WeightedUF(N);
    }

    public void remove(int x) {
    uf.union(x, x+1);
    }

    public int successor(int x) {
    return uf.root(x + 1);
    }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s