How to design a stack such that we can get the minimum in O(1)?

Suppose we want to find the minimum element available in a stack at any point of time. The most trivial and common method would be to traverse the entire stack and keep a record of the least element encountered. At the end, we can return this element.

This method no doubt is easy, but it consists of traversing the entire stack again and again, which can lead to time complexities.

Thus, we need to optimize it, and it can be done with a very neat little trick:-

ALGORITHM:-

Take an auxiliary stack which maintains the minimum of all values in the stack. Also assume that, each element of the stack is less than its below elements. Let us call this auxiliary stack as the min stack.

When we POP, the main stack, POP the min stack too. When we push the main stack, push either the new element or the current minimum, whichever is lower. At any point of time, if we want to get the minimum – then we just need to return the top element from the min stack. Let us take some example and trace it out. Initially let us assume that we have pushed 2,6,4,1 and 5.
Based on the above algorithm, the min stack will look like:-

After popping twice we get

Thus, as we see, the TOP of the MIN STACK will always point to the minimum element till latest and we can get it in O(1).

Here is an implementation of the same:-

#include<stdio.h>
#include<stdlib.h>

struct stackNode
{
    int data;
    struct stackNode * next;
};

struct stackNode * push(struct stackNode * top, int element)
{
    struct stackNode * temp = (struct stackNode *)malloc(sizeof(struct stackNode));
	if(!temp)
	{
		printf("STACK OVERFLOW");
		return top;
	}
    temp -> data = element;
    temp -> next = top;
    return temp;
}

int getMinimum(struct stackNode * s)
{
	// since the top node points to the minimum value, we can return the TOP element.
	return s->data;
}

int main(void)
{
	struct stackNode * mainStack = NULL;
	struct stackNode * minStack = NULL;

	mainStack = push(mainStack,2);
	int min = mainStack -> data;

	minStack = push(minStack, min);

	int i = 4;

	// input elements 6, 4, 1, 5
	while(i--)
	{
		int x;
		scanf("%d",&x);

		//we directly push this number on the main STACK
		mainStack = push(mainStack, x);

		if(min > x)
			min = x;

		//we need to push only the minimum number found till now.
		minStack = push(minStack,min);
	}

	printf("the minimum is :- ",getMinimum(minStack));

	i = 2;
	// let us POP 2 times
	while(i--)
	{
		//Call the POP function on both the stacks
		mainStack = mainStack -> next;
		minStack = minStack -> next;
	}

	printf("the minimum is :- ",getMinimum(minStack));

	return 0;
}