Minimum Stack O(1)

Algorithm/Insights

1. Maintain another field in the stack elements, which tracks minimum
2. Everytime there is a push, compare with the minimum from the top element
3. If the pushed element lesser than the top's minimum, then update minimum when pushed.

Code Snippet

			
package com.ideserve.virendra.questions;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * <br><br>
 * Minimum Stack- Dynamic Programming Solution</b><br>
 * Implement a stack with operations min, push, pop and top in O(1)
 * <br><br>
 * <a href="https://www.youtube.com/watch?v=8Ub73n4ySYk">Minimum Stack Solution Youtube Link</a> 
 * @author Virendra
 *
 *
 */
 
 public class MinStack {
	
	Node top;
	
	public void push(int x)
	{
		if(top == null)
		{
			top = new Node(x);
		}
		else
		{
			Node temp = new Node(x);
			temp.next = top;
			temp.min = Math.min(top.min, x);
			top = temp;
		}
	}
	
	public void pop()
	{
		if(top == null)
		{
			System.out.println("Stack empty!");
			return;
		}
		
		top = top.next;
	}
	
	public int top()
	{
		if(top == null)
		{
			System.out.println("Stack empty!");
			return Integer.MAX_VALUE;
		}
		
		return top.value;
	}
	
	public int min()
	{
		if(top == null)
		{
			System.out.println("Stack empty!");
			return Integer.MAX_VALUE;
		}
		
		return top.min;
			
	}
	
	public static void main(String args[])
	{
		MinStack mStack = new MinStack();
		mStack.push(7);
		mStack.push(8);
		System.out.println(mStack.min());
		mStack.push(5);
		mStack.push(9);
		System.out.println(mStack.min());
		mStack.push(5);
		mStack.push(2);
		System.out.println(mStack.min());
		mStack.pop();
		mStack.pop();
		System.out.println(mStack.min());
	}
	
	
}

class Node {
	int value;
	int min;
	Node next;
	
	Node(int x)
	{
		value = x;
		next = null;
		min = x;
	}
}
		

Order of the Algorithm

Time Complexity is O(1)
Space Complexity is O(n)