You can make it so that finding a free slot is always O(1). Keep another array that is a stack of available slot indexes. When you need a free slot, pop off an index and use that slot. When you're done with a slot, push its index on the stack.