insert, delete, max in O(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.

The following solution uses O(1) extra memory and O(1) time for max, push and pop operations. Keep a variable max which will keep track of the current max element at any particular time. Lets utilize the fact that when max is updated, all the elements in the stack should be less than the new max element. When a push operation occurs and the new element(newElement) is greater than the current max we push the max + newElement in the stack and update max = newElement.

When we are doing a pop operation and we find that the current popped element is greater than the current max then we know that this is place where we had updated our stack to hold max+elem. So the actual element to be returned is max and max = poppedElem - max.

For eg. if we are pushing 1, 2, 3, 4, 5 the stack and max variable will look like below:

MAIN       Value of MAX
+---+      +---+
| 9 |      max = | 5 |
| 7 |      max = | 4 |
| 5 |      max = | 3 |
| 3 |      max = | 2 |
| 1 |      max = | 1 |
+---+      +---+

Now lets say we pop an element, we will basically pop, max element(since top > max) and update the max element to (top-max)

MAIN       Value of MAX
+---+      +---+
| 7 |      max = | 4 | = (9-5)
| 5 |      max = | 3 |
| 3 |      max = | 2 |
| 1 |      max = | 1 |
+---+      +---+

Now lets say we are pushing numbers 5, 4, 3, 2, 1, the stack will look like:

MAIN       Value of MAX
+---+      +---+
| 1 |      max = | 5 |
| 2 |      max = | 5 |
| 3 |      max = | 5 |
| 4 |      max = | 5 |
| 5 |      max = | 5 |
+---+      +---+

When we pop, the top of stack is popped since top < max, and max remains unchanged.

Following is a pseudo code for each of the operation for better insight.

Elem max;
void Push(Elem x){
    if x < max :
        push(x);
    else{
        push(x+max);
        max = x;
    }
}
Elem Pop(){
    Elem p = pop();
    if |p| < |max|:
        return p;
    else{
        max = p - max;
        return max;
    }
}
Elem Max(){
    return max;
}

push and pop are normal stack operations. Hope this helps.

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

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

insert, delete, max in O(1)

Related

Recent Posts