Min-Max Stack

Assume you have infinite memory. Design a algorithm using stacks that can find the minimum and maximum at any point while reading an infinite sequence of numbers in least possible time.

Eg. 5, 9, 2, 35, 23, 1, ...
After 3rd element, the algorithm would tell min = 2, max = 9
After 6th element, algorithm would tell min = 1, max = 35

Solution 1 :

Since there is no limitation on space, so we can maintain 3 stacks.

• 1st stack will be the main stack in which we are pushing all elements
• 2nd stack will contain maximum elements up to that point
• 3rd stack will contain minimum elements up to that point.

So range can also be found in O(1) time, by popping from 2nd stack & 3rd stack and taking their difference.

Complexities :

• Time : O(1)
• Space : Unlimited

Code :

template <class T>
class range_stack<T> {

private :

stack<T> main, min, max;

public :

int push(T value){

main.push(value);

if(main.empty()){

min.push(value);
max.push(value);

}
else {

if(min.top() > value)

min.push(value);

else

min.push(min.top());

if(max.top() < value)

max.push(value);

else

max.push(max.top());

}

}

T pop(){

T tmp = main.top();
main.pop();
min.pop();
max.pop();
return tmp;

}

T range(){

return max.top() - min.top();

}

}