algorithm - insert, delete, max in O(1)

Question

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

Answer 1

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.