An approach that uses O(1) time and O(n) extra space is discussed here.

In 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.

**Important Points:**

- Stack doesn’t hold actual value of an element if it is minimum so far.
- Actual minimum element is always stored in minEle

**Illustration**

- Number to be Inserted: 3, Stack is empty, so insert 3 into stack and minEle = 3.
- Number to be Inserted: 5, Stack is not empty, 5> minEle, insert 5 into stack and minEle = 3.
- Number to be Inserted: 2, Stack is not empty, 2< minEle, insert (2*2-3 = 1) into stack and minEle = 2.
- Number to be Inserted: 1, Stack is not empty, 1< minEle, insert (2*1-2 = 0) into stack and minEle = 1.
- Number to be Inserted: 1, Stack is not empty, 1 = minEle, insert 1 into stack and minEle = 1.
- Number to be Inserted: -1, Stack is not empty, -1 < minEle, insert (2*-1 – 1 = -3) into stack and minEle = -1.

- Initially the minimum element minEle in the stack is -1.
- Number removed: -3, Since -3 is less than the minimum element the original number being removed is minEle which is -1, and the new minEle = 2*-1 – (-3) = 1
- Number removed: 1, 1 == minEle, so number removed is 1 and minEle is still equal to 1.
- Number removed: 0, 0< minEle, original number is minEle which is 1 and new minEle = 2*1 – 0 = 2.
- Number removed: 1, 1< minEle, original number is minEle which is 2 and new minEle = 2*2 – 1 = 3.
- Number removed: 5, 5> minEle, original number is 5 and minEle is still 3

**Implementation:**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
package stackandqueues; import java.util.Stack; public class GetMinimum { Stack<Integer> stack = new Stack<Integer>(); int minElement; public static void main(String[] args) { GetMinimum getMin = new GetMinimum(); // TODO Auto-generated method stub getMin.push(3); getMin.push(5); getMin.getMin(); getMin.push(2); getMin.push(1); getMin.getMin(); getMin.pop(); getMin.getMin(); getMin.pop(); } private void pop() { // TODO Auto-generated method stub if(stack.isEmpty()) { System.out.println("Stack is empty"); return; } System.out.println("Most top element is removed"); int t = stack.peek(); stack.pop(); // Minimum will change as the minimum element // of the stack is being removed. if(t<minElement) { System.out.println("The minElement is "+minElement); minElement = 2*minElement - t; } else { System.out.println(t); } } private void getMin() { // TODO Auto-generated method stub if(stack.isEmpty()) { System.out.println("Stack is empty"); } else { System.out.println("Minimum element is "+minElement); } } private void push(int i) { // TODO Auto-generated method stub if(stack.isEmpty()) { minElement = i; stack.push(i); System.out.println("Element inserted: "+i); return; } // If new number is less than minElement if(i < minElement) { stack.push(2*i - minElement); minElement = i; System.out.println("Element inserted: "+i); } else { stack.push(i); System.out.println("Element inserted: "+i); } } } |

**Result:**

1 2 3 4 5 6 7 8 9 10 11 |
Element inserted: 3 Element inserted: 5 Minimum element is 3 Element inserted: 2 Element inserted: 1 Minimum element is 1 Most top element is removed The minElement is 1 Minimum element is 2 Most top element is removed The minElement is 2 |