Minimum Stack O(1)

Implement a stack with operations min, push, pop and top in O(1)


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Preparing for interviews? IDeserve team is here to help.




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.


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




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)


Contribution

  • Sincere thanks from IDeserve community to Virendra Karappa for compiling current post.

    Virendra Karappa

    Ninja Programmer