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.

Answer 2

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.

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

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 5

Below program keeps track of max elements in stack in such a way that any point of time the top pointer would give us the max in the stack : So, max would be O(1), and we can find max by max[N]

ITEM   MAX

+---+  +---+
| 1 |  | 1 |
| 10|  | 10|
| 9 |  | 10|
| 19|  | 19| <--top
+---+  +---+

Java Program:

public class StackWithMax {

private int[] item;
private int N = 0;
private int[] max;

public StackWithMax(int capacity){
    item = new int[capacity];//generic array creation not allowed
    max = new int[capacity];
}

public void push(int item){
    this.item[N++] = item;
    if(max[N-1] > item) {
        max[N] = max[N-1];
    } else {
        max[N] = item;
    }
}

public void pop() {
    this.item[N] = 0;
    this.max[N] = 0;
    N--;
}

public int findMax(){
    return this.max[N];
}
public static void main(String[] args) {
    StackWithMax max = new StackWithMax(10);
    max.push(1);
    max.push(10);
    max.push(9);
    max.push(19);
    System.out.println(max.findMax());
    max.pop();
    System.out.println(max.findMax());


}

}

Answer 6

Like some have already pointed out, the question lacks some information. You don't specify were to insert/delete, nor the nature of the data we are dealing with.

Some ideas that could be useful: You say,

insert/delete/maximum operation in O(1)

note that if we can insert, delete, and find maximun in O(1), then we can use this hipotetical technique to sort in O(n), because we can insert the n elements, and then take max/delete and we get them all sorted. It's proven that no sorting algorithm based in comparisons can sort in less than O(nlogn), so we know that no comparison based aproach will work. In fact, one of the fastest known ways of doing this is the Brodal queue, but it's deletion time exceeds O(1).

Maybe the solution is something like a radix tree, were the complexity of all these operations is related to the key length as oposed to the amount of keys. This is valid only if they let you bound the key length by some other number, so you can consider it constant.

But maybe it wasn't something that generic. Another interpretation, is that the insert/delete are the ones of a classic stack. In that restricted case, you can use the double stack solutiom that Can Berk Güder gave you.

Answer 7

The best thing exists is: Insert in O(1) Delete in O(logn) Max/Min in O(1)

But to do that the insert function must create a link chain and you will also need an extra thread. The good news is that this link chain function also works in O(1) so it will not change the O(1) of insert.

Delete function doesnt break the link chain.

If the target of your delete is the max or min then the delete will be executed in O(1)

The data structure is a mix of an avl tree and a linked list.

The nature of a true delete is such that you cannot make it work in O(1). Hash tables which work with O(1) delete dont have the cabability to hold all the inputs.

Answer 8

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.