insert, delete, max in O(1)

Question

Can someone tell me which data structure supports insert/delete/maximum operation in O(1) ?

Thanks Ram

Answer 1

If you are using only comparisons, you would be hard pressed to find such a data structure.

For instance you could insert n elements, get max, delete max etc and could sort numbers in O(n) time, while the theoretical lower bound is Omega(nlogn).

Answer 2

A hash table might support insert/delete in O(1), no clue about maximum though. You'd probably need to keep track of it yourself somehow.

Answer 3

@KennyTM's comment points out an important missing detail - insert where, and delete from where. So I am going to assume that you always want to insert and delete only from one end like a stack.

Insertion (push) and Delete (pop) are O(1).

To get Max in O(1), use an additional stack to record the current max which corresponds to the main stack.

Answer 4

This is a classical interview question, and is usually presented like this:

Devise a stack-like data structure that does push, pop and min (or max) operations in O(1) time. There are no space constraints.

The answer is, you use two stacks: the main stack, and a min (or max) stack.

So for example, after pushing 1,2,3,4,5 onto the stack, your stacks would look like this:

MAIN   MIN
+---+  +---+
| 5 |  | 1 |
| 4 |  | 1 |
| 3 |  | 1 |
| 2 |  | 1 |
| 1 |  | 1 |
+---+  +---+

However, if you were to push 5,4,3,2,1, the stacks would look like this:

MAIN   MIN
+---+  +---+
| 1 |  | 1 |
| 2 |  | 2 |
| 3 |  | 3 |
| 4 |  | 4 |
| 5 |  | 5 |
+---+  +---+

For 5,2,4,3,1 you would have:

MAIN   MIN
+---+  +---+
| 1 |  | 1 |
| 3 |  | 2 |
| 4 |  | 2 |
| 2 |  | 2 |
| 5 |  | 5 |
+---+  +---+

and so on.

You can also save some space by pushing to the min stack only when the minimum element changes, iff the items are known to be distinct.