CareerCup

stack 1		stack 2
	
push(5)		push(5)
push(2)		push(2)	(in stack2 if new data is less than top of stack then push new one)
push(7)		push(2)
push(20)	push(2)
push(9)		push(2)
push(1)		push(1)

now if you pop an element from stack 1, pop from second stack which is having min value till that point

stack 1		stack 2
pop()=>1	pop()=>1	1 is min so far
pop()=>9	pop()=>2	2 is min so far
pop()=>20	pop()=>2

Maintain 2 stacks : Normal and minimumNoTracker.
Push: Everytime you push element in Normal stack, check the topmost element in MinimumNoTracker stack and if topmost element is greater than current, push the new element on MinimumNoTracker as well.
Pop: Everytime you pop element from Normal stack, check if it is same as top element of MinimumNoTracker, if yes pop out that number.

Can't we use a sort on initial input if we have them stored. then push them in decreasing order ?

if we already have the problem where we are randomly generating number than putting them in stack, we need to use atleast 3 stacks, and this problem will pretty much looks like Towers of Hanoi problem, and we can use a recursive approach to solve it.

Basically you to create a variable in you stack impl class. Every time to push and entry it should compare to this variable if it is min then store that min number. Also you add getMin an isMin API to get and compare again this number....

why cant we implement min-heap here:
For insertion: insert at the top and min-heapify
For popping: take the top element and min-heapify

If insertion and popping is O(1), then insert n numbers, and pop the same n numbers. By the claim both operations would be O(n). Since popping gives the minimum number, we get a sorted list. Great, sorting in linear time.

Idea is to write a new function pushbubble() using push(), where an element is inserted into its sorted position (situation similar to insertion sort). In that case, the top element will always be the minimum element.
Full working code here : awesomecoder.blogspot.com/2012/08/push-elements-into-stack-pop-should.html

void stack::pushbubble(int elem){
 int temp;
 if(!this->isempty()){
  temp = this->pop();
  if(temp > elem){
   this->push(temp);
   this->push(elem);
  } else {
   this->pushbubble(elem);
   this->push(temp);
  }
 } else {
  this->push(elem);
 }
}

Like others have explained, maintain two stacks; one with the value and one with the min value in the other stack.

template <typename T>
class MinStack {
private:
  std::stack<T> stack;
  std::stack<T> min;
public:
  MinStack() {}
  void push(T elem) {
    stack.push(elem);
    min.push(std::min(elem, min.top());
  }
  std::pair<T, T> popValAndMin() {
    T val = stack.top();
    T minVal = min.top();
    stack.pop();
    min.pop();
    return std::make_pair(val, minVal);
  }
};

Tag

maintain 2 stacks

i wont write any code yet, but the list should be sorted first. And we know that stack is last one in and first out, so numbers are put into stack in descending order. Popping the smallest element will take o(1) since the smallest will be the last one in.

If this was possible, you could sort in linear time.

Maintain each stack node with data and min value (beneath itself).

Basically, you can build a priority queue using Fibonacci Heap. Operation on F Heap is O(1).