Initializing an Array in O(1) Time

Initializing an array usually takes time, when we spend time setting bits of data at a specific location in memory to . Given that our machine memory can contain junk data, how do we build a data structure(an array) that initializes in time, has updates, queries, and space (worst case analysis here). We can assume that each array entry fits in bits, and that fits in one machine word.

We use a total of three arrays to accomplish this. We do not set any of these arrays to initially. In the first array, we store our data entries, each of bits. In the second, we store the position indices of those that we have visited, in order (so that if we see an element here, we know that the element in that position in the first array is correct). At this point in time, if we also maintain a separate integer , to count the number of unique indices we have visited already, we can solve this array construction problem in updates, by iterating through the second array from positions to , so that when we are queried, we can figure out if the element at the position index is correct by linear searching through the second array.

To avoid this problem of having to do a linear search, if we wish to figure out if position has been visited before, we store it’s position in a third array at position . Now, if we need to update or query the array at position , we check index in our third array, then check that value is less than our current second array size . If it is indeed less than , then we check if the value at the index in array two is indeed . If it is, we know that the value at index in the first array is correct, and we can update accordingly. If it is not inside, we can either output in the case of a query, or in the case of an update, simply increment , and update the appropriate values in the first, second, and third arrays.