{"id":12008,"date":"2023-01-24T07:34:20","date_gmt":"2023-01-24T07:34:20","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=12008"},"modified":"2023-09-22T10:31:30","modified_gmt":"2023-09-22T10:31:30","slug":"how-to-implement-min-stack","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/how-to-implement-min-stack\/","title":{"rendered":"How to Implement Min Stack"},"content":{"rendered":"

\"\"<\/p>\n

In this article, we will learn what is Min Stack and what are the different ways to implement the min stack.<\/p>\n

What is Min Stack?<\/h2>\n

The Min Stack is a special type of stack that support all the stack operations such as push(), pop(), isEmpty(), and isFull(). In addition, Min Stack also supports one additional function getMin(), which is used to retrieve the minimum element from the stack that is why it is also called the minimum stack.<\/p>\n

Lets understand what is the min stack using an example.<\/h3>\n
stack = [30, 10, 50, 20, 40]<\/code><\/pre>\n
For this stack, if we call getMin() function then it will return 10.<\/p>\n
Now, let\u2019s see how a stack looks after performing the pop() operation two times.<\/p>\n
stack = [10, 50, 20, 40]  ( 1st pop() operation)\nstack = [50, 20, 40]  (2nd pop() operation )<\/code><\/pre>\n
If we call getMin() function this time then it will return 20.<\/p>\n
Different Ways to Implement Min Stack:<\/h2>\n
We already know what is the min stack. Now. let\u2019s see how to implement the min stack using various approaches.<\/p>\n
Approach 1:<\/h3>\n
In this approach, we store the pair as the current value and the value of the minimum so far. This means the first element of the pair will store the value and the second element will store the minimum till now. Let\u2019s understand this approach with an example dry run.<\/p>\n
Dry run:<\/strong><\/p>\n
Initial stack=[]\nOperation: push(20)\nstack=[(20,20)]\nHere, we have inserted pair (20,20) into the stack, the first element is the value and the second value is the minimum stack value till now.<\/code><\/pre>\n
Operation: push(30)<\/strong><\/p>\n
stack=[(30,20), (20,20)]\nHere, we have inserted pair (30,20) into the stack, the first element is the value (30) and the second value is the minimum stack value(20) till now.<\/code><\/pre>\n
Operation: push(10)<\/strong><\/p>\n
stack=[(10,10), (30,20), (20,20)]\nHere, we have inserted pair (10,10) into the stack, the first element is the value (10) and the second value is the minimum stack value(10) till now.<\/code><\/pre>\n
Operation: push(40)<\/strong><\/p>\n
stack=[(40,10), (10,10), (30,20), (20,20)]\nHere, we have inserted pair (40,10) into the stack, the first element is the value (40) and the second value is the minimum stack value(10) till now.<\/code><\/pre>\n
\t\t\t\t\t\t