CareerCup

Each stack element will have two part
1.data.
2.pointer to maximum element.

Push: check if data < top()->maxpointer->data, then the new data will also point to the same max.Othersiwe its max pointer will point to itself.

Pop: No checking :)

Max: return top()->maxpointer->data.

use one more stack, for storing max values...

Actually we can use a heap to simulate a stack or a queue.
As new numbers are arrived assign a key to it such that key = key of previous element + 1. key of first element = 1. now build a max heap based on this key value. This facilitates constant time functions as asked above.

My solution was same as Sumit solution.

Actually what I feel using another stack is not so much impressive. Because you
cannot call GetMax() implementation will be on that stack which is not correct.
AND also holding pointer to max-node is not good because of memory.

If : Its a class ie: class CStack, then we can create a member variable 'max_value'
which holds the max value stored in the stack.and Obj.GetMax() will return the value.

Sorry for 2nd sentence. Correct is : Because you cannot call GetMax() with different stack pointer. Or your GetMax() implementation will be on different stack,not the original stack.

My solution is same as xyz.. except that xyz has forgotten to take care of removing the max value.

For which you will need a doubly linked list for the stack, so that we can remove the maxpointer
a) change the prevptr to the maxpointer->nextptr
b) and change the top->maxpointer = top->prevptr->maxpointer.

I guess this question is already posted before .. one elegant solution is to maintain 2 elements ( for each push operation that you do on the stack ) , one is the element and the other is max
lets say , you try to push 3 ,4 7 , 2 , 5 in that order

push(3) stack top has (3,3) = (elem,max)
push(4) stack top has (4,4)
push(7) stack top has (7,7)
push(2) stack top has (2,7)
push(5) stack top has (5,7)

the idea is to compare the element that you are pushing on to the top of stack with the already existing max element , and then decide the new max element .

import java.util.Stack;

public class MaxStack {
private static class Node {
int data;
int max;
}

Stack<Node> stack;

public MaxStack(){
stack = new Stack<Node>();
}

public int push (int data){
Node n = new MaxStack.Node();
n.data = data;
if (stack.empty() || stack.peek().max <= n.data) {
n.max = n.data;
} else n.max = stack.peek().max;

stack.push(n);
return data;

}

public int pop(){
return stack.pop().data;
}

public int peek(){
return stack.peek().data;
}

public int getMax(){
return stack.peek().max;
}

public boolean empty() {
return stack.empty();
}
}

Reposting with whitespaces

import java.util.Stack;

public class MaxStack {
	private static class Node {
		int data;
		int max;
	}
	
	Stack<Node> stack;

	public MaxStack(){
		stack = new Stack<Node>();
	}

	public int push (int data){
		Node n = new MaxStack.Node();
		n.data = data;
		if (stack.empty() || stack.peek().max <= n.data) {
			n.max = n.data;
		} else  n.max = stack.peek().max;

		stack.push(n);
		return data;
		
	}

	public int pop(){
		return stack.pop().data;
	}
	
	public int peek(){
		return stack.peek().data;
	}

	public int getMax(){
		return stack.peek().max;
	}

	public boolean empty() {
		return stack.empty();
	}

For GetMax, everytime when a element is pushed, top of stack should be compared with MAX ptr.
eg: 5 6 3 2 7

PUSH   MAX   STACK
5      5     5
6      6     5 6
3      6     5 6 3
2      6     5 6 3 2
7      7     5 6 3 2 7

I think the solution where we keep the current value and the max value of the elements below it is the best.

People here are telling that only storing the max value is enough, but that is not enough the reason being, if the max value is popped out[using a pop operation] then we need to rescan the stack to get the next max value which takes o(n) time. So best is to have each element store the current value and max value till that point.

The above solution all has flaws. all 3 ops need to be o(1). However, push() and pop(), might change the MAX value. We have to get a sorted strucuter for getMax() to be o(1), then no sort function is o(1) --> push() and pop() not o(1).
Any solutions?

Correct solution is the one posted above. Save the max so far for each node pushed. Calculating the new max is just a simple comparision of previous max and value of the node being pushed.

Simple solution would be to use max heap. push and pop operations does not mean that one need to use only stack or array. The max heap can be represented using array, the root node of heap will always return max value. push and pop operations can be used to add/remove node at the end of the heap.