CareerCup

Have an extra field in stack that tracks the min so far.

To keep the minimum takes time!
When adding a new entry to the stack it is easy. But when removing - it is the hard nut.
To keep a heap - well, pop will remove the entry from the stack but heapify has a cost of O(log(N)) as far as I know. So pop is not O(1) then.
Did I miss something?

struct StackNode
{
int data;
StackNode *min;
StackNode *prev;
StackNode(int data = INT_MAX, StackNode *ptr = NULL, StackNode *minPtr = NULL) : data(data),prev(ptr),min(minPtr) {}

};
void Push(int data,StackNode **headPtr)
{
if(*headPtr == NULL)
{
*headPtr = new StackNode(data,NULL,NULL);
(*headPtr)->min = *headPtr;
return;
}
else
{
StackNode *temp = new StackNode(data,*headPtr,NULL);

if((*headPtr)->min->data < data)
{
temp->min = (*headPtr)->min;
}
else
{
temp->min = temp;
}

(*headPtr) = temp;

}

}
void Pop(StackNode ** headPtr)
{
if(*headPtr == NULL)
{
printf("Stack is Empty");
}
else
{
StackNode *temp = *headPtr;
(*headPtr) = (*headPtr)->prev;
delete temp;
temp = NULL;
}

}

int Top(StackNode *headPtr)
{
if(headPtr == NULL)
{
printf("Stack is Empty");
}
else
{
printf("Data At Top = %d\n",headPtr);
return headPtr->data;
}

}

int FindMin(StackNode *headPtr)
{
if(headPtr == NULL)
{
printf(" \nStack is Empty\n");
return -1;
}
else
{
return headPtr->min->data;
}
}

class MinStack {
	
	private def data = []
	private def minData = []
		
	def findMin(){		
		checkEmpty()		
		return minData[minData.size()-1]
	}
	
	void push(val){
		data += val
		
		if( minData.isEmpty() ){
			minData.push(val)
		}
		else if( minData[minData.size()-1] > val  ){
			minData.push(val)
		}		
	}

	def pop(){
		
		checkEmpty();
		
		def val = data.pop()
		
		if( val == minData[minData.size()-1] ){
			minData.pop()
		}
		
		return val		
	}
	
	private void checkEmpty(){
		if( data.isEmpty() ){
			throw new IllegalStateException("stack is empty")
		}
	}	
}

You can accomplish O(1) time complexity, by using extra space to keep track of the minimum, during push and pop operations.

Method 1:
Push the minimum so far and the new element in the stack as a pair, when you add the element to the stack. This will require double the space size of the stack, because for each element, you also save the minimum. Therefore, the space complexity is Big_Theta(n)


Method 2:
Keep another stack and push the min values along with the count of the min as a pair to the let's say, min_stack. For instance, when you push the element to the stack, if it's the new minimum, then push it to the min stack and set the count 1, if the new element is equal to the min value at the top of the min_stack, then increment the count.

In the second method, the implementation is a little bit more complex compared to the 1st method because of the cases when you do push and pop on the main stack. Heuristically, the additional space will be reduced compared to method 1, but in the worst case, where each element pushed is less then the previous element, it is still Big_Theta(n)

public class MinList<T extends Comparable> {
    public MinList() {
        super();
    }

    public MinList(T data) {
        this.setData(data);
    }
    private MinList<T> next;
    private T min;
    private T data;
    private MinList<T> head;

    public static void main(String[] args) {
        MinList<Integer> minList = new MinList<Integer>();
        int[] a = {10,5,20,6,4,30,1};
        for(int i:a) {
            minList.push(i);
        }
        System.out.println(minList.getMinimum());
        System.out.println(minList.pop());
        System.out.println(minList.pop());
        System.out.println(minList.getMinimum());
    }

    public void push(T data) {
        MinList<T> head = this.getHead();
        MinList<T> item = new MinList<T>(data);
        if (this.getHead() == null) {
            this.setHead(item);
            item.setMin(item.getData());
        } else {
            item.setNext(this.getHead());   
            this.setHead(item);
            if(item.getData().compareTo(item.getNext().getMin()) < 0) {
                item.setMin(item.getData());
            }
            else {
                item.setMin(item.getNext().getMin());
            }
        }
    }
    
    public T pop() {
        MinList<T> item = this.getHead();
        this.setHead(item.getNext());
        item.setNext(null);
        return item.getData();
    }
    
    public T getMinimum() {
        return this.getHead()!=null?this.getHead().getMin():null;
    }

    public void setNext(MinList<T> next) {
        this.next = next;
    }

    public MinList<T> getNext() {
        return next;
    }

    public void setData(T data) {
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public void setHead(MinList<T> head) {
        this.head = head;
    }

    public MinList<T> getHead() {
        return head;
    }

    public void setMin(T min) {
        this.min = min;
    }

    public T getMin() {
        return min;
    }
    
    public String toString() {
        return this.getData()!=null?this.getData().toString():null;
    }
}

It depends on how far we would like to go on "Min Value". Let's assume we would like to know the min value at all time, i.e., after the deletion as well. We can maintain a min-heap of the entire dataset in addition to the stack. In contrast, if we would like know the kth smallest, we can maintain a max-heap of size k of the entire dataset. Pseudo code is something like this:

for(i=0;i<k;i++)
 heap[i]=a[i];
buildMaxHeap(heap,k);
for(i=k;i<n;i++)
{
  if(a[i]<heap[0])
 {
    heap[0]=a[i];
    MaxHeapify(heap,0);
 }
}

hence the min value is always heap[0].
We should remove the deleted values from the heap upon their removal from the stack.

@Selmeczy, you are absolutely right, I forgot the delete operation is also required to be O(1) and thought only about the min value. Thanks for pointing it out!

We can address this issue by keeping the addresses of the nodes in the heap, in a hash table i.e., table[value]=node_address_in_heap. Then delete becomes o(1) as well. However, the maintenance of the heap is still demanding O(lg n) time :)

Lately I've been spending some time on designs. Here's a sample generic implementation, that develops upon standard Stack design:

/*
Base Stack class
*/
#define DEFAULTSIZE 10

template<class T>
class Stack{
	protected:
	T *elems;
	int top;
	int max;

	public:
	Stack(int size = DEFAULTSIZE):max(size), top(-1){
		elems = new T[max];
	}

	~Stack(){
		delete elems;
	}

	virtual void push(const T& val);

	virtual void pop();

	bool isEmpty();

	bool isFull();

	const T& getTop();
};

template<class T>
bool Stack<T>::isEmpty(){
	return top < 0;
}

template<class T>
bool Stack<T>::isFull(){
	return (top == (max-1));
}

template<class T>
void Stack<T>::push(const T& val){
	if(isFull())
		return;
	elems[++top] = val;
}

template<class T>
const T& Stack<T>::getTop(){
	int val;
	if(isEmpty())
		return val;
	return elems[top];
}

template<class T>
void Stack<T>::pop(){
	if(isEmpty())
		return;
	--top;
}

/*
Derived MinStack class
adding desired extra constraints
*/

template<class T>
class MinStack:public Stack<T>{
	T * minElems;
	int minTopIdx;
	
	public:
	MinStack(int size = DEFAULTSIZE):Stack<T>(size), minTopIdx(-1){
		minElems = new T[this->max];
	}

	~MinStack(){
		delete minElems;
		~Stack<T>();
	}

	virtual void push(const T& val);
	virtual void pop();
	const T& getMin();
};

template<class T>
void MinStack<T>::push(const T& val){
	if(this->isFull())
		return;
	
	T minVal = (this->isEmpty())?val:getMin();
	if(minVal >= val){
		//push onto both stacks
		minElems[++minTopIdx] = val;
	}
	this->elems[++(this->top)] = val;
}

template<class T>
void MinStack<T>::pop(){
	if(this->isEmpty())
		return;

	if(this->getTop() == getMin()){
		--minTopIdx;
	}
	--this->top;
}

template<class T>
const T& MinStack<T>::getMin(){
	T dummy;
	if(this->isEmpty())
		return dummy;
	return minElems[minTopIdx];
}

Hope it helps.

Further ideas: :)
Rather than having MinStack, derive Stack with a generic constraint.