using System;

using System.Collections;

​

/*Design a Data Structure SpecialStack that supports all the stack operations like 

push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should return

minimum element from the SpecialStack. All these operations of SpecialStack must be O(1).

To implement SpecialStack, you should only use standard Stack data structure and no other data structure like arrays, list, .. etc.*/

​

/* SOLUTION 1 (easier O(1), and O(n) space */

/*

Solution: Use two stacks: one to store actual stack elements and the other as an auxiliary stack to store minimum values. The idea is to do push() and pop() operations in such a way that the top of the auxiliary stack is always the minimum. Let us see how push() and pop() operations work.

Push(int x) // inserts an element x to Special Stack 

1) push x to the first stack (the stack with actual elements) 

2) compare x with the top element of the second stack (the auxiliary stack). Let the top element be y. 

…..a) If x is smaller than y then push x to the auxiliary stack. 

…..b) If x is greater than y then push y to the auxiliary stack.

int Pop() // removes an element from Special Stack and return the removed element 

1) pop the top element from the auxiliary stack. 

2) pop the top element from the actual stack and return it.

The step 1 is necessary to make sure that the auxiliary stack is also updated for future operations.

int getMin() // returns the minimum element from Special Stack 

1) Return the top element of the auxiliary stack.

We can see that all the above operations are O(1). 

Let us see an example. Let us assume that both stacks are initially empty and 18, 19, 29, 15, and 16 are inserted to the SpecialStack. 

*/

​

/* SOLUTION 2 (easier O(1), and O(1) extra space */

​

/*

n this article, a new approach is discussed that supports minimum with O(1) extra space. We define a variable minEle 

that stores the current minimum element in the stack. Now the interesting part is, how to handle the case when minimum element is removed. 

To handle this, we push “2x – minEle” into the stack instead of x so that previous minimum element can be retrieved using current minEle and its value stored in stack. 

Below are detailed steps and explanation of working.

*/

​

/*

Push(x) : Inserts x at the top of stack.

​

​

​

​

If stack is empty, insert x into the stack and make minEle equal to x.

If stack is not empty, compare x with minEle. Two cases arise:

If x is greater than or equal to minEle, simply insert x.

If x is less than minEle, insert (2*x – minEle) into the stack and make minEle equal to x. For example, let previous minEle was 3. Now we want to insert 2. We update minEle as 2 and insert 2*2 – 3 = 1 into the stack.

Pop() : Removes an element from top of stack.

​

Remove element from top. Let the removed element be y. Two cases arise:

If y is greater than or equal to minEle, the minimum element in the stack is still minEle.

If y is less than minEle, the minimum element now becomes (2*minEle – y), so update (minEle = 2*minEle – y). 

This is where we retrieve previous minimum from current minimum and its value in stack. For example, let the element to be removed be 1 and minEle be 2. We remove 1 and update minEle as 2*2 – 1 = 3.

*/

​

/*

When element to be inserted is less than minEle, we insert “2x – minEle”. 

The important thing to notes is, 2x – minEle will always be less than x (proved below), 

i.e., new minEle and while popping out this element we will see that something unusual has happened as the popped element is less than the minEle. So we will be updating minEle.

*/

​

public class Program

{

    static void Main(string[] args)

    {

        var stack = new SpecialStack();

        stack.Push(10);

        stack.Push(20);

        stack.Push(3);

        stack.Push(3);

        Console.WriteLine($"Min: {stack.GetMin()}");

        Console.WriteLine($"Popped: {stack.Pop()}");

        Console.WriteLine($"Popped: {stack.Pop()}");

        Console.WriteLine($"Min: {stack.GetMin()}");

        Console.WriteLine($"Popped: {stack.Pop()}");

        Console.WriteLine($"Popped: {stack.Pop()}");

​

    }

    class SpecialStack 

    {

        private Stack _stack = new Stack();

        private int _min_element = int.MaxValue;    

        public void Push(int value)

        {

            if (value < _min_element)

            {

                _stack.Push(2*value -_min_element);

                // store previous mean and value in stack, and min in variable. 

                _min_element = value;

            }

            else

                _stack.Push(value);

        }

        public int Pop()

        {

            // need to know if we are popping the min value

            var y = (int)_stack.Pop();

            if (y < _min_element) // condition for min value

            {

                var to_return = _min_element;

                //value is less than min_element, new min_value = 2*min_element - y 

                _min_element = 2*_min_element - y;

                return to_return;                                    

            }

            return y;

        }

        public int GetMin()

        {

            return _min_element;

        }

    }

}