Interview Questions 5: Successor with delete

We try to relate the solution to the problem of Successor with delete to Union-Find algorithm here and discuss how to relate them and make it more straightforward in the first place from two different angles: 1) Analyze it in a recursive way and give an informal proof; 2)  Draw it out by hand.

Problem Definition:

Note this problem is from the “Algorithm Part 1″ on Coursera. The detailed description is as follows:

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.

Analysis:

Well, I think the Union-Find approach to solve this problem should already be known to quite a number of people, the challenge would be how to relate the solution to Union-Find approach at the first place without any hints about Union-Find. I first directly give the approach and then discuss how to relate it to Union-Find from two different angles to help consider the approach in Union-Find way more naturally.

The algorithm to solve the problem is to use union-find with path compression only (i.e., do not use weighted quick union).

  1.  Treat Root(x) as the successor of x
  2.  Delete(x) is equivalent to Union(x, x + 1) and specifically in Union(x, x+1) we need to change Root(x) to Root(x+1)
  3.  Successor(x) is equivalent to return Root(x)

For the step 2, because weighted quick union might change Root(x+1) to Root(x), so we cannot use that, the union rule is fixed in this problem by always changing Root(x) to Root(x+1), but since we adopt path compression, all the operations in the above three steps take logarithmic time.

1) First angle to understand and relate the above steps to Union-Find:

To understand the correctness and the intuition behind the above approach, we could first consider the set as a forest: only the root of each tree in the forest are those nodes which are NOT deleted. So at first, nothing is deleted, and each node is a single node tree. To delete a node value x, it first must be in the set, so it has to be a root of some tree, by our approach above, delete x means Append Root(x) = x to Root(x+1), so the delete becomes intuitive: just make a node Root(x) = x not root, this informally prove that step 2 is correct and making sense.

Now we need to check step 3. Let’s think about it in this way:

Initially if x is in the set, then the successor is itself, else if x is deleted, the potential successor is x + 1, and for x + 1, if x + 1 is in the set,  it means we never do Union(x + 1, x + 1 + 1) before, that is, Root(x + 1) == x + 1, so we just return x + 1, if we have already done Union(x + 1, x + 1 + 1) before, it means x + 1 is also deleted, we try x + 2, recursively, it becomes finding the root in the tree.

2) Second angle to Understand and relate the above steps to Union-Find:

Just draw it out by hand, and you could see that both the 1 an 2 ‘s successor is 3, for other values 0, 3, 4, 5 the successors are themselves:

initially:  0 1 2 3 4 5

delete 2:   0  1   3   4   5
                  /
                 2

Delete 1:   0   3   4   5
               / \
              2   1

Conclusion:

To summarize the post, we discussed how we relate the solution to the problem of Successor with delete to Union-Find algorithm here and how to relate them and make it more straightforward in the first place from two different angles: 1) Analyze it in a recursive way and give an informal proof; 2)  Draw it out by hand.

Written on September 15, 2014