Data structure for finding max, inserting and deleting in O(1) and O(n) space

Question

This is an interview question. I need to implement a data structure that supports the following operations:

1. Insertion of an integer in $O(1)$

2. Deletion of an integer (for example, if we call delete(7), then 7 is deleted from the data structure, if the integer 7 exists in it) in $O(1)$.

3. Return maximum integer in the data structure (without deleting it) in $O(1)$.

You can also use up to $O(n)$ space.

I thought of something similar to this question, but here we have $O(\mathrm{log}\ n)$.

Do you know how can we implement these operations in $O(1)$?

Edit: forgot important thing - you can assume the numbers that will be inserted are integers in the range $[0,n]$.

• greybeard: (Retrun?) (the purpose here proposition?) Is this to be a set or a multiset / bag (insert 7 twice, delete it once: still in)?
• John: @greybeard, it's a multi-set. Nothing to return in the insertion and deletion, only at the maximum operation.

Answer 1

Suppose we have such data structure. We can find in $O(1)$ the max, delete the max in $O(1)$ and repeat it $n$ times. Hence, we can sort $n$ numbers in $O(n)$. Therefore, constructing such data structure must take $\Omega(n\log(n))$ (like sorting, in general, can't be done better than $n\log(n)$. Hence, you might have some constraint on data). Also, as deleting is in $O(1)$, means it must be found. Hence, Searching and Finding is in $O(1)$.

Therefore, you must know the position of each value (something like counting sort, but with this constraint that $max <= n$ to take the $O(n)$ space!). Hence, you can act like a counting sort by saving the max value in a variable besides the array, by accepting some constraint on data (not in general).

• John: Thanks, indeed I forgot an assumption about the integers and edited the post. However, I still don't find a way to implement the operations as needed. Can you elaborate more on how you can do this with something that is similar to counting sort (thought of counting array, but it doesn't help by itself)?
• OmG: @John my pleasure. By the new assumption, it's exactly the same as counting sort plus a variable to store max and update after each inserition. read more counting sort on Wikipedia.
• John: how do you update the maximum when you delete an element from the data structure? in this case I see only wallking backward in the counting array till I find a number with is not zero (and that isn't O(1) )
• OmG: @John you don't need this. As I've said, you've stored the max in constructing time, in a variable. When you delete a number, just check with the value of maximum in that varible and do the proper act in $O(1),ドル
• John: @OmG, I agree with smart28 - don't see it as well. Can you please describe in your post a pseudo code of how you implement these operations in O(1)?

Answer 2

You can implement first 2 ops easily by creating an array from 0 to max and store counts of added/removed items there. Regarding the maximum....

I think the question is just little tricky. Since max is constant, you can iterate whole array and it would be also in O(1).

• John: How can you iterate the whole array in O(1)?
• smrt28: "you can assume the numbers that will be inserted are integers in the range [0, N]" - N is constant, no matter how many items are inserted. Just think how it would work if N=1. Clear?