Data structure for maintaining large space-efficient filtered array

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.

• I don't think it's possible to support constant time deletion and constant time lookup of the i-th element. You have to update the indices somehow, that should take at least log time. – adrianN Aug 13 '13 at 12:05
• That would be my guess too. But this question was posed as a challenge to me and I still don't have a definite answer. :) – gkb0986 Aug 13 '13 at 12:46
• The challenge doesn't mention constant time deletion, so I'd assume it's not necessary. But recreating the array each time you delete an element is probably too costly. – gkb0986 Aug 13 '13 at 12:48
• Which challenge? You have to reference those! By the by, what's wrong with an array? You need to clarify the question: what does "space efficient" mean? What does "array" mean exactly here? Are the time restrictions worst- or average-case? Is amortisation allowed? What is a "filter" here? Do you do lookup by index or key? – Raphael Aug 13 '13 at 14:44
• @Raphael sure. The challenge was actually posed to me in person and I'm not sure if I can insert a reference to that. I don't even know the poser's name accurately. Space-efficient: Any space not used by elements of the array that have not been deleted by the filter, let's call it extra space, should be O(1). Array in the context of this problem means an array-like data structure where you can get the i'th element in constant time. You lookup by index here. I suspect amortization should be fine. The filter takes each element of collection and returns 0/1 corresponding to delete/no delete. – gkb0986 Aug 13 '13 at 15:55

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.

Lookup of i'th element in the array should be constant time

The only thing I could think of is a hashtable

The space formerly occupied by deleted elements in the array should be available for further use.

This could be achieved easily by having an array of pointers or a queue of pointers that way whenever you decide to create a new item, you can choose to pop from the queue or array. When you delete/don't need the object in the array, you enqueue it. If the queue or array is empty, then you create a new object.

• "This could be achieved easily by having an array of pointers or a queue of pointers that way whenever you decide to create a new item, you can choose to pop from the queue or array or if they are empty, then you create a new object." This is nice. But I wonder if you can free it up for other routines within the same process that do not use this array or queue for memory allocation. "The only thing I could think of is a hashtable" I considered it, but hashtables aren't space efficient in general, unless you're willing to tolerate a lot of collisions. That's why I was't inclined to use them. – gkb0986 Aug 13 '13 at 14:16
• Splay trees are cool. I like that they use temporal locality. But they still have worst case O(log n) lookup time. – gkb0986 Aug 13 '13 at 14:18
• You can also try avl tree. Here is one I recently implemented actually the worst case lookup time for splay trees is O(n). But worst case for avl trees is always O(log n) – smac89 Aug 13 '13 at 14:19
• Thanks for the link. However, I'm concerned that avl trees will give you O(log n) lookup time and not satisfy the requirements. – gkb0986 Aug 13 '13 at 14:21
• If you find a data structure that does O(1) query lookup and is not a hashtable, I would be interested so please keep this page updated EDIT: O(log n) lookup is not so bad; to look up an item in an avl tree of 1 million items means you have to do 19 comparisons in the worstcase. Another suggestion is a van Emde Boas tree but it is only good for numbers – smac89 Aug 13 '13 at 14:22