Theory and Practice: Array puzzle solution

Theory and Practice: Array puzzle solution

The hard nut is, of course, initializing in constant time an array of size n. We can try to keep track of a set of indexes that are initialized. This reduces the problem to implementing a set of integers that supports make_empty, insert, and contains operations in constant time.

• array_init: allocate an array of size n, make an empty set
• array_set: set the element in the array and insert the index in the set of indexes
• array_get: if the index is not in the set return the default value, otherwise read from the array

It remains now to see how to implement such a set. A hash-table is not good because it is randomized (and many implementations offer only amortized constant time). A bitmap does insert and contains in constant time, but we can't make an empty set quickly. A list of integers can do insert and make_empty in constant time, but we can't determine quickly if an integer is in the list. Can we get the best of both? Yes, with two tricks:

1. If we represent the list as an array plus a counter then we can index it quickly. So we might be able to do the contains operation in constant time if we know where to look.
2. In a bitmap we don't have to store only bits: We can store the information we need for the previous observation. And here's the crux: If we do so we do not need to initialize it!

I'll leave it here. If you still have trouble writing the code, let me know.

PS: Rustan said he vaguely remembers reading this in Knuth, but he wasn't sure.

Edit: Cosmin pointed me to a more clear explanation. (I didn't read it: It's a bit long.)

Read full article from Theory and Practice: Array puzzle solution