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