That removal does not work if the max has been seen multiple times. Say, you have sequence "1 2 3 3". When you build the max stack, it will become "1 2 3". Now you remove the top 3 off the stack, it is equal to max, so you remove it from max as well. So you have stack "1 2 3" and max stack "1 2" - wrong. there are two solutions of that issue - first one: always push a new max, might it be the same as before. When popping, always pop the max stack as well. Second solution (more space friendly): Push a new max if the coming value is greater OR EQUAL as the current max, so the repeating max values will repeat in the max stack. Now you can safely remove the max from the max stack if the popped value is equal to max.

Yes, I should have been more clear. If a pushed value is >= max push it on the max stack.

1 actual stack (s1) + 1 max stack (s2) void push(int x){ push x into s1 if x>=getMax() push x into s2 } void pop(){ if s1.top==s2.top s2.pop() s1.pop() } int getMax(){ if max stack is empty return INT_MIN else return s2.top }