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:

### Like this:

Like Loading...

*Related*

[…] Algorithm, Part I – Successor with delete […]

Seem that the successor of x is actually the largest object in the component which x is a member of + 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?

You need 2 additional list: prececessor and successor list

public void elimina(int i){

array[i]=-1;

int predecessor = predecessor_list[i];

successor_list[predecessor] = successor_list[i];

predecessor_list[successor_list[i]]=predecessor;

}

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);

}

}