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]$.

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).

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).