Implement stack (push, pop and findmin) in O(1)

Question

I have already seen two stack implementation of this question but I am really confused as how one could get O(1) operation. consider following example:

S1[3542761986759]
S2[3332221111111]

The idea/algorithm here is

1. Push element E on S1
2. Check to see if top of S2 >= E and if true, insert E on S2

But when getMin is called, we return top of S2 but that leaves S2 in weird state as S2 contains repeated current min elements, so the solution is to search next minimum element in S2 and return it. This is O(n).

Can anyone please help me to understand the solution?

Answer 1

Using a linked list store the current minimum value. When you add a new number it looks at the previous min and changes the current min to the current value if the current value is lower.

E.g... Assume you have the data: 3, 6, 4, 2, 7, 1. Then this is what the list would look like

value|min

3|3 -> 6|3 -> 4|3 -> 2|2 -> 7|2 -> 1|1

That'll keep track of the mins as you push/pop items. Granted you'll need to have a root node and a node designated as a "footer" so you can access the end in O(1).

Or you could go backwards with it and add things to the front and change the root node every insert... that would work too. It would be something like this:

1|1 -> 7|2 -> 2|2 -> 4|3 -> 6|3 -> 3|3

Then you wouldn't need the "footer" node.

Both of these will keep track of the current min value for when the value was pushed. That way when the actual min value is pushed, it will know what the second min value was in O(1).

Answer 2

I am posting the complete code here to find min and mx in a stack. Time complexity will be O(1)

package com.java.util.collection.advance.datastructure;

/** * * @author vsinha * */ public abstract interface Stack {

/**
 * Placing a data item on the top of the stack is called pushing it
 * @param element
 * 
 */
public abstract void push(E element);


/**
 * Removing it from the top of the stack is called popping it
 * @return the top element
 */
public abstract E pop();

/**
 * Get it top element from the stack and it 
 * but the item is not removed from the stack, which remains unchanged
 * @return the top element
 */
public abstract E peek();

/**
 * Get the current size of the stack.
 * @return
 */
public abstract int size();


/**
 * Check whether stack is empty of not.
 * @return true if stack is empty, false if stack is not empty
 */
public abstract boolean empty();

}

package com.java.util.collection.advance.datastructure;

@SuppressWarnings("hiding") public abstract interface MinMaxStack extends Stack {

public abstract int min();

public abstract int max();

}

package com.java.util.collection.advance.datastructure;

import java.util.Arrays;

/** * * @author vsinha * * @param */ public class MyStack implements Stack {

private E[] elements =null;
private int size = 0;
private int top = -1;
private final static int DEFAULT_INTIAL_CAPACITY = 10;


public MyStack(){
    // If you don't specify the size of stack. By default, Stack size will be 10
    this(DEFAULT_INTIAL_CAPACITY);
}

@SuppressWarnings("unchecked")
public MyStack(int intialCapacity){
    if(intialCapacity <=0){
        throw new IllegalArgumentException("initial capacity can't be negative or zero");
    }
    // Can't create generic type array
    elements =(E[]) new Object[intialCapacity];
}

@Override
public void push(E element) {
    ensureCapacity();
    elements[++top] = element;
    ++size;
}

@Override
public E pop() {
    E element = null;
    if(!empty()) {
        element=elements[top];
        // Nullify the reference
        elements[top] =null;
        --top;
        --size;
    }
    return element;
}

@Override
public E peek() {
    E element = null;
    if(!empty()) {
        element=elements[top];
    }
    return element;
}

@Override
public int size() {
    return size;
}

@Override
public boolean empty() {
    return size == 0;
}

/**
 * Increases the capacity of this <tt>Stack by double of its current length</tt> instance, 
 * if stack is full 
 */
private void ensureCapacity() {
    if(size != elements.length) {
        // Don't do anything. Stack has space.
    } else{
        elements = Arrays.copyOf(elements, size *2);
    }
}

@Override
public String toString() {
    return "MyStack [elements=" + Arrays.toString(elements) + ", size="
            + size + ", top=" + top + "]";
}

}

package com.java.util.collection.advance.datastructure;

/** * Time complexity will be O(1) to find min and max in a given stack. * @author vsinha * */ public class MinMaxStackFinder extends MyStack implements MinMaxStack {

private MyStack<Integer> minStack;

private MyStack<Integer> maxStack;

public MinMaxStackFinder (int intialCapacity){
    super(intialCapacity);
    minStack =new MyStack<Integer>();
    maxStack =new MyStack<Integer>();

}
public void push(Integer element) {
    // Current element is lesser or equal than min() value, Push the current element in min stack also.
    if(!minStack.empty()) {
        if(min() >= element) {
            minStack.push(element);
        }
    } else{
        minStack.push(element);
    }
    // Current element is greater or equal than max() value, Push the current element in max stack also.
    if(!maxStack.empty()) {
        if(max() <= element) {
            maxStack.push(element);
        }
    } else{
        maxStack.push(element);
    }
    super.push(element);
}


public Integer pop(){
    Integer curr = super.pop();
    if(curr !=null) {
        if(min() == curr) {
            minStack.pop();
        } 

        if(max() == curr){
            maxStack.pop();
        }
    }
    return curr;
}


@Override
public int min() {
    return minStack.peek();
}

@Override
public int max() {
    return maxStack.peek();
}


@Override
public String toString() {
    return super.toString()+"\nMinMaxStackFinder [minStack=" + minStack + "\n maxStack="
            + maxStack + "]" ;
}

}

// Test program

package com.java.util.collection.advance.datastructure;

import java.util.Random;

public class MinMaxStackFinderApp {

public static void main(String[] args) {
    MinMaxStack<Integer> stack =new MinMaxStackFinder(10);
    Random random =new Random();
    for(int i =0; i< 10; i++){
        stack.push(random.nextInt(100));
    }
    System.out.println(stack);
    System.out.println("MAX :"+stack.max());
    System.out.println("MIN :"+stack.min());

    stack.pop();
    stack.pop();
    stack.pop();
    stack.pop();
    stack.pop();

    System.out.println(stack);
    System.out.println("MAX :"+stack.max());
    System.out.println("MIN :"+stack.min());
}

}

Output:

MyStack [elements=[99, 76, 92, 49, 89, 88, 93, 33, 0, 30], size=10, top=9] MinMaxStackFinder [minStack=MyStack [elements=[99, 76, 49, 33, 0, null, null, null, null, null], size=5, top=4] maxStack=MyStack [elements=[99, null, null, null, null, null, null, null, null, null], size=1, top=0]] MAX :99 MIN :0 MyStack [elements=[99, 76, 92, 49, 89, null, null, null, null, null], size=5, top=4] MinMaxStackFinder [minStack=MyStack [elements=[99, 76, 49, null, null, null, null, null, null, null], size=3, top=2] maxStack=MyStack [elements=[99, null, null, null, null, null, null, null, null, null], size=1, top=0]] MAX :99 MIN :49

Let me know if you have any issues.

Thanks, VIKASH SINHA

Answer 3

This is not possible. Otherwise you'd be able to implement comparison sorting in linear time: First push all elements in O(1) each, O(n) total time, and then n times get the minimum in O(n) total time.

As it is known that O(n log n) is a lower bound for comparison sorting, a solution with O(1) push and findmin can't exist.

Edit: Replaced "sorting" by "comparison sorting" as noted by Gabe.