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:

Pingback: Algorithm I, Part I — Union By Height | Data Nest

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

SaurabhHow 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?

michael maghella (@michaelmaghella)You need 2 additional arrays: list of predecessor and successors.

public void delete(int i){

array[i]=-1;

int predcessor = predecessor_list[i];

successor[predecessor] = successor_list[i];

predecessor_list[successor_list[i]]=predecessor;

}

michael maghella (@michaelmaghella)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;

}

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

}

}

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

}

}