# 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:

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

1. Wayne

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

2. Saurabh

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

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

4. Roman

Noy sure if I have posted it. To understand how it works – just wriye down small example on the paper and do few successor() and remove operations on 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);
}
}