*The problem was solved by Hadi Moshayedi.*

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:

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

## No comments:

## Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.