Getting the Min element on the stack in O (1) Time

Question

The reason I ask this question is because I cannot understand why, as I think, it cannot be applied to this particular question

"How would you create a stack that, in addition to push and pop, also has a min function that returns the minimum element? Push, pop and min should work O (1) times. "

My basic solution: It would not be possible if we had a variable in the stack class, that whenever we push an item onto the stack, we check less than our min variable. If it assigns the value min, if not ignore.

You will still get O (1) as a function of min;

int getMinimum(){ return min; } 

Why is this solution never mentioned, or what is the error with the way I think?

Answer 1

This will not work if you pop the numbers from the stack.

Ex. 2,4,5,3,1. After you press 1, what is your minimum?

The solution is to keep a stack of lows, not just a single value. If you come across a value that is less than the current minimum, you need to push it onto the mini-stack.

Ref.

 Push(4): Stack: 4 Min-stack: 4 Push(2): Stack: 4 2 Min-stack: 4 2 Push(2): Stack: 4 2 2 Min-stack: 4 2 2 Push(5): Stack: 4 2 2 5 Min-stack: 4 2 2 Push(3): Stack: 4 2 2 5 3 Min-stack: 4 2 2 Push(1): Stack: 4 2 2 5 3 1 Min-stack: 4 2 2 1 Pop(): Stack: 4 2 2 5 3 Min-stack: 4 2 2 Pop(): Stack: 4 2 2 5 Min-stack: 4 2 2 Pop(): Stack: 4 2 2 Min-stack: 4 2 2 Pop(): Stack: 4 2 Min-stack: 4 2 Pop(): Stack: 4 Min-stack: 4 

Answer 2

Use a linked list to keep track of the minimum value that will be the head.

Note that linkedlist.app = append (we put the value in the tail). linkedlist.pre = prepend (we put the value as the head of the linked list)

open class Stack {

 int[] elements; int top; Linkedlists min; public Stack(int n) { elements = new int[n]; top = 0; min = new Linkedlists(); } public void realloc(int n) { int[] tab = new int[n]; for (int i = 0; i < top; i++) { tab[i] = elements[i]; } elements = tab; } public void push(int x) { if (top == elements.length) { realloc(elements.length * 2); } if (top == 0) { min.pre(x); } else if (x < min.head.data) { min.pre(x); } else { min.app(x); } elements[top++] = x; } public int pop() { int x = elements[--top]; if (top == 0) { } if (this.getMin() == x) { min.head = min.head.next; } elements[top] = 0; if (4 * top < elements.length) { realloc((elements.length + 1) / 2); } return x; } public void display() { for (Object x : elements) { System.out.print(x + " "); } } public int getMin() { if (top == 0) { return 0; } return this.min.head.data; } public static void main(String[] args) { Stack stack = new Stack(4); stack.push(2); stack.push(3); stack.push(1); stack.push(4); stack.push(5); stack.pop(); stack.pop(); stack.pop(); stack.push(1); stack.pop(); stack.pop(); stack.pop(); stack.push(2); System.out.println(stack.getMin()); stack.display(); } 

}

Answer 3

I found this solution here

 struct StackGetMin { void push(int x) { elements.push(x); if (minStack.empty() || x <= minStack.top()) minStack.push(x); } bool pop() { if (elements.empty()) return false; if (elements.top() == minStack.top()) minStack.pop(); elements.pop(); return true; } bool getMin(int &min) { if (minStack.empty()) { return false; } else { min = minStack.top(); return true; } } stack<int> elements; stack<int> minStack; }; 

Answer 4

We define the variable minEle, which stores the current minimum element on the stack. Now the interesting part is how to handle the case when the minimum element is removed. To handle this, we push "2x - minEle" onto the stack instead of x so that the previous minimum element can be obtained using the current minEle and its value stored on the stack. Below are detailed steps and explanations for the work.

Push (x): Inserts x at the top of the 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 the top of the 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. / Java program to implement a stack that supports // getMinimum() in O(1) time and O(1) extra space. import java.util.*; // A user defined stack that supports getMin() in // addition to push() and pop() class MyStack { Stack<Integer> s; Integer minEle; // Constructor MyStack() { s = new Stack<Integer>(); } // Prints minimum element of MyStack void getMin() { // Get the minimum number in the entire stack if (s.isEmpty()) System.out.println("Stack is empty"); // variable minEle stores the minimum element // in the stack. else System.out.println("Minimum Element in the " + " stack is: " + minEle); } // prints top element of MyStack void peek() { if (s.isEmpty()) { System.out.println("Stack is empty "); return; } Integer t = s.peek(); // Top element. System.out.print("Top Most Element is: "); // If t < minEle means minEle stores // value of t. if (t < minEle) System.out.println(minEle); else System.out.println(t); } // Removes the top element from MyStack void pop() { if (s.isEmpty()) { System.out.println("Stack is empty"); return; } System.out.print("Top Most Element Removed: "); Integer t = s.pop(); // Minimum will change as the minimum element // of the stack is being removed. if (t < minEle) { System.out.println(minEle); minEle = 2*minEle - t; } else System.out.println(t); } // Insert new number into MyStack void push(Integer x) { if (s.isEmpty()) { minEle = x; s.push(x); System.out.println("Number Inserted: " + x); return; } // If new number is less than original minEle if (x < minEle) { s.push(2*x - minEle); minEle = x; } else s.push(x); System.out.println("Number Inserted: " + x); } }; // Driver Code public class Main { public static void main(String[] args) { MyStack s = new MyStack(); s.push(3); s.push(5); s.getMin(); s.push(2); s.push(1); s.getMin(); s.pop(); s.getMin(); s.pop(); s.peek(); } } 

How does this approach work?

When the inserted element is less than minEle, we insert "2x - minEle". It is important to note that 2x - minEle will always be less than x (proved below), i.e. The new minEle and, choosing this element, we will see that something unusual happened, because the popped element is smaller than minEle. So we will update minEle

How is 2 * x - minEle less than x in push ()?

x <minEle, which means x - minEle <0

// Add x on both sides

x - minEle + x <0 + x

2 * x - minEle <x

We can conclude 2 * x - minEle <new minEle

If you find that element (y) is smaller than the current minEle, we will find a new minEle = 2 * minEle - y.

---

Like the previous minimum element, prevMinEle is, 2 * minEle - y?

in pop () is a popped item?

// We hit y like 2x - prevMinEle. Here

// prevMinEle is the minEle before inserting y

y = 2 * x - prevMinEle

// The value of minEle was equal to x minEle = x.

new minEle = 2 * minEle - y

  = 2*x - (2*x - prevMinEle) = prevMinEle // This is what we wanted