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

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

  1. 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. 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