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:

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

1. Wayne says:

Seem that the successor of x is actually the largest object in the component which x is a member of + 1

2. 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?

3. 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;
}

4. 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);
}
}