CareerCup

Is that possible? unless you keep extra variable for stroing min value. Update this value when ever you insert and pop an element from stack.

whenever we push an element on to stack , have an extra variable min with the struct element .. compare the element which you are pushing on to the stack with the element's min field on top of the stack . This will ensure that top element's min field does have the min value of the stack .. ( this is with out considering space complexity as a constraint) .

Well, if that was the case, lets say we had 
0
5
3

If we pop 0, then, we have
5
3

So, now, your element to store the temp variable is invalid.

But, if we had another stack to store the least variable and a pointer to mapping the the corresponding element in the original stack, it's possible to keep track of the least element in the stack and pop it off the smallest stack when the actual element is popped.

So, 
insert 3

actual stack      smallest stack
------------      --------------
3                 3


insert 5:

actual stack      smallest stack
------------      --------------
5                 3 
3


insert 0:

actual stack      smallest stack
------------      --------------
0                 0
5                 3
3


pop 0:


actual stack      smallest stack
------------      --------------
5                 3
3                 

pop 5:


actual stack      smallest stack
------------      --------------
3                 3

easy question, just have another atom which takes min number. it takes a time every atom pushed. but you can take min element with 0(1)

Answer posted by Balaji is good. Use two extra stacks for max and min. You can get max and min in O(1).

while pushing just keep the min elemen

What about min heap?
a heap node can have 1) element, 2) ptr to keep min heap structure, and 3) ptr to keep track of stack data structure.

Bala Ji Solution seems correct. but it violates space constraint requirement.

In case of below push we need stack of equivalent size.

9,8,7,6,5,4,3,1

Any other idea.

Amit, you are right. The problem is all about the stack.
What I want to say is modified min heap structure.
To be more concise, heap node might contain 1) element and 2) ptr to next stack top along with the current stack top.
As we know, min heap structure does not need to have any ptr when array is used.
it's because it is a complete binary tree.

I think Bala Ji solution is great. :)

We can have stack with each entry having additional pointer. The stack functionality of push and pop will be as normal. But every time we push/pop, this additional pointer needs to be updated to point to next larger value

I doubt if this question is correct as a given stack contains unsorted elements and we will have to see the elements atleast once to get the min/max so we cant avoid the O(n) time anyways.

How about we maintain an internal linked list for min element. Each time we push we create accordingly push it at the head/insert it at the appropriate place on the internal linked list. Thus min would be O(1) and when we pop, we compare it with the head of the linked list, if it is "the" element which is popped then we can delete the head from our internal linked list and make the second min element as our new top element.

SNL: the question is about stacks and you're not supposed to use liknedlist to get this problem done.

You can find the solution to this problem in Advanced Data structures book by peter brass ..i didnt get any online link , but you can search that book to find the solution its a real nice book i got pdf version in google itself .

Balaji's solution is the way to go.

just keep a pointer to the smallest element...each time u insert compare it wid the value being inserted..if its smaller, shift your pointer else leave it

The problem says to find the min in O(1) time. If taken literally, then we can maintain the extra variable as suggest before. Then whenever popped we adjust the min by some scanning. Then still we would be able to maintain the condition of O(1) complexity of finding the min. Not every time we are going to pop the min element. So amortized complexity of pop might be (and should be) less than O(n). So dont worry much about the pop.

make each element of the stack to store two values
stack value,min value at the time of its insertion
and we need one more int value to keep the current min.
while pushin we can update the current min
while poping (if we are poping the min value) we can get the previous min value by reading the top element's min.

Java Implementation of Minimum stack using LinkedList (not the class) Push, Pop and getMinimum() requires O(1).

class Node {
	Node next;
	Node nextMin;
	int value;

	public String toString() {
		return value + "";
	}
}

class MinStack {
	Node top;
	Node minNode;
	int size;

	public void push(int data) {
		Node node = new Node();
		node.value = data;
		if (top != null) {
			node.next = top;
			if (node.value < minNode.value) {
				node.nextMin = minNode;
				minNode = node;
			}
		} else {
			minNode = node;
		}
		top = node;
		size++;
	}

	public Node pop() {
		if (top == null) {
			return null;
		}
		Node tmp = top;
		if (minNode.value == tmp.value) {
			minNode = tmp.nextMin;
		}
		top = tmp.next;
		size--;
		return tmp;
	}

	public Node getMinNode() {
		return minNode;
	}
}

public class MinStackTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		MinStack minStack = new MinStack();
		minStack.push(10);
		minStack.push(2);
		minStack.push(12);
		minStack.push(3);
		minStack.push(0);
		minStack.push(1);
		int size = minStack.size;
		for (int i = 0; i < size; i++) {
			System.out.println("Before:" + minStack.getMinNode());
			System.out.println("Popped:" + minStack.pop());
			System.out.println("After:" + minStack.getMinNode());
		}
	}
}