[Solved]: Data structure for maintaining large space-efficient filtered array

Problem Detail: 

How does one implement a space efficient data structure that satisfies the requirements below?

1. You have a large array
2. You have a filter which tells you which elements in that large array are to be deleted
3. Lookup of i'th element in the array should be constant time
4. 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.

Asked By : gkb0986

Answered By : D.W.

There is a simple and clean solution that satisfies all of your requirements.

To delete elements, you scan the set of array indices (from 1 to $n$), querying the filter on each and deleting each element that is to be deleted, compacting the array as you go (to shift everything after the deleted element forward one slot). The deletion operation can be implemented in $\Theta(n)$ time, with a single linear scan. This satisfies all of your requirements. (Note that you did not specify any restriction on the running time of the deletion operation.) In particular, it is space-efficient: it does not require any extra space (it has 0 space overhead, since after deletion, all of the space that's not in use for storing undeleted array elements is immediately available for other use). Looking up the $i$th element of the array takes constant time, thanks to the compaction: you just index into the $i$th element of the compacted array.

If for some reason this solution is not acceptable to you, then you need to re-think the requirements more thoroughly and edit the question to pose the exact set of requirements more carefully.

Given the problem as you've stated it, I don't think it will be possible to do better than this trivial solution. You can't do better than $\Theta(1)$ time for lookup. You can't do better than 0 space overhead. And I don't think you can do better than $\Theta(n)$ time for deletion, given how you specified the interface to deletion (which works by specifying a filter that is an oracle that, on input $i$, tells you whether index $i$ should be deleted or not). Even just figuring out which elements of the collection to delete requires querying the filter on all $n$ possible indices, which takes $\Theta(n)$ time. So, I don't think you can do any better than $\Theta(n)$ time for the deletion operation -- and in particular, I don't think you can do any better than the above scheme, at least not with this specification of how the filter is provided.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13732