How does one implement a space efficient data structure that satisfies the requirements below?
- You have a large array
- You have a filter which tells you which elements in that large array are to be deleted
- Lookup of i'th element in the array should be constant time
- The space formerly occupied by deleted elements in the array should be available for further use.
I've explored approaches ranging from bloom filters to trees, but they violate one requirement or the other.
EDIT: Further clarification.
Space-efficient: Any space not used by elements of the array that have not been deleted by the filter, which we can term extra space or space for book-keeping, should be $O(1)$. We can probably relax this to allow any solution that gets close to $O(1)$ extra space. $O(n)$ extra space is undesirable.
Array in the context of this problem is an array-like collection where you can get the $i$th element in constant time. You lookup by index here.
I suspect amortized performance bounds should be fine.
The filter takes each element of collection and returns 0/1 corresponding to delete/no delete.