{"id":1565,"date":"2024-02-02T13:00:00","date_gmt":"2024-02-02T13:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=1565"},"modified":"2024-02-03T07:30:04","modified_gmt":"2024-02-03T07:30:04","slug":"min-stack-problem","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/min-stack-problem\/","title":{"rendered":"Min Stack Problem (C++, Java, Python)"},"content":{"rendered":"\n<p>The stack is a data structure that operates in LIFO order. This means last in, first out. Let\u2019s understand through an example: In a school bus, the last person to enter will be the first to exit.  In this article, we will discuss the different solutions to the question Min Stack problem from Leetcode.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>What is the Min Stack problem?<\/strong><\/h2>\n\n\n\n<p><strong>In the Min Stack problem, you are required to perform various operations like push, pop, topmost element, and minimum element from the stack. You must perform all the operations in constant time, O(1).<\/strong><\/p>\n\n\n\n<p>This includes tasks like:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Add elements into the stack.<\/li>\n\n\n\n<li>Remove or pop elements from the stack.<\/li>\n\n\n\n<li>Print the topmost element from the stack.<\/li>\n\n\n\n<li>Or to get the minimum element from the stack.<\/li>\n<\/ul>\n\n\n\n<p>Let&#8217;s consider an example where you begin with an empty stack and perform the following operations:&nbsp; [\u201cpush, 1\u201d, \u201dpush, 2\u201d, \u201dpop\u201d, \u201cpush, 3\u201d, \u201ctop\u201d, \u201cmin\u201d].<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>After the initial push 1, the stack becomes&nbsp;<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/k7giYQoVRh1CqX79YdoI-U_3e6A1NvAuETgflDPlUVMdGvyIUeToCGFnP-TmFBFn0veiBsKLtAZWXpdwTeGdX-B4jP8oBNR0LV5zabrdUtfHG1fIuL7mLPnwFuhJiHpbkcCaeiD702ECviLQWp5MRxE\" alt=\"Push 1 in stack\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>After the next push 2, the stack becomes<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/4HnfJJO9BhTjKlolABrAavhbS9b9gD0mfDfuurv_XBuahpE64w_531x-5uGdMt8PRDBPFDHMXX-9SthKRF0kkKqMZo7-Uvt0SaV5N-oWbwXnjzL3DjQjj9CpC16dzucjfzXfLcwCpvmZeRMNMhhvDPs\" alt=\"Push 2 in stack\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>At the next pop remove the top element from the stack.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/QO_ethZrzp4tnmg4ONToErph5JobOowNhh1_jlQfgB6AsKXTHEe56rHKhWNlghQcTOv0qRkLYgt0l4b1GvAJ8ZBlDFMThIkFu8BlzFrUaanKX-ENFZPTwcriXIO_CLvfVctz2ejBQQ9oTUf0Fg176To\" alt=\"2 is popped out\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Now push 3 in the stack<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/e7peu7ZCO_tYzFczDZHwa5GNgpN-aMCCXqCMf4qFMM4oj9-aOY75rE28znq--8uxi3_tHDFeQSSZPsoahp2O8kSaAawKmqRT3THCAEyg9n37N56H4eHPShyLjG-g9ms97V8WpU6cd29ERxO02OzTkhc\" alt=\"Push 3 in stack\"\/><\/figure>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Print the top element from the stack in this case top element is 3.<\/li>\n\n\n\n<li>Print minimum from the stack. The minimum is 1 so it prints 1.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/X2aRQDpkCYMKtRfrmsnaAC0P0w0ZeGiYsLF_a1eigdy-PQUhJjpIJg2al2UeCrRiQND4kuq8cwSB1jM0_h7H11kUfCIVa4X-e6nJHKb77BUX9EiP6-JwAN5BXfY_sAzvZ16uZNvm85Xg5JSgfKIrj2Y\" alt=\"Print minimum from stack\"\/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Using Two-Stack Approach<\/strong><\/h2>\n\n\n\n<p>This approach uses two stacks: one takes care of the minimum element till now, while the other is to store all the elements. Whenever we have to print the minimum element, we print that from the min_stack. If we have to print the topmost element of the stack, we use the regular stack.&nbsp;<\/p>\n\n\n\n<p>Let&#8217;s examine each step with the same example&nbsp; [\u201cpush, 1\u201d, \u201dpush, 2\u201d, \u201dpop\u201d, \u201cpush, 3\u201d, \u201ctop\u201d, \u201cmin\u201d].<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Create two stacks min_stack and main_stack.<\/li>\n\n\n\n<li>If the operation is &#8216;push,&#8217; then push the value into the main_stack and check whether the min_stack is empty or if the top value of the min_stack is greater than the current value. If it is, push the value into the min_stack; otherwise, do not.<\/li>\n\n\n\n<li>If the operation is \u201cpop\u201d, then check if the min_stack top value is the same as of main_stack if so, remove an element from both the stacks, otherwise remove only from main_stack.<\/li>\n\n\n\n<li>If the operation is \u2018top,\u2019 then print the topmost element from the main_stack.<\/li>\n\n\n\n<li>If the operation is \u2018Min,\u2019 then print the topmost element from the min_stack.<\/li>\n<\/ol>\n\n\n\n<p>As in this approach, we are not using any loop in any of the operations so, the time complexity is <strong>O(1)<\/strong> which is required. As we are using two stacks to solve the problem, the space complexity is <strong>O(2*n)<\/strong>, where n represents the number of values we need to add.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Using Only One Stack to Solve Min Stack<\/strong><\/h2>\n\n\n\n<p>As in the above approach, we are using two stacks which increases our space complexity. We can solve the Min Stack problem with one stack also. Let&#8217;s examine each step:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Create an empty stack and a variable that stores the minimum value at each point.<\/li>\n\n\n\n<li>Now, if it is the \u201cpush\u201d operation, check if the stack is empty or the minimum value is less than the current value. If it is, push the value to the stack.<\/li>\n\n\n\n<li>If not then push (2*current_value)-min and update the minimum value to the current value. We are doing this because if we take out this element in the operation \u2018pop\u2019 we can get the previous min value.<\/li>\n\n\n\n<li>If it is the \u2018pop\u2019 operation, check whether the topmost element is greater than the minimum value. If it is, then pop directly otherwise update the minimum value to ((2*minimum_value) &#8211; topmost value). Pop the element.<\/li>\n\n\n\n<li>If it is the \u2018top\u2019 operation then check if the topmost element is greater than the minimum value if it is then print the topmost element otherwise print the minimum value.<\/li>\n\n\n\n<li>If it is the \u2018min\u2019 operation then print the minimum value.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>C++ Code<\/strong><\/h3>\n\n\n\n<p>Check the C++ solution below:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;C++&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\n\n\/\/ creating a stack.\nstack&lt;long long int&gt;s;\n\/\/ creating a variable that stores minimum value\nlong long int mn;\n\n\/\/ push function\nvoid push(long long int value){\n    if (s.size()==0) {\n        s.push(value);\n        mn = value;\n    } else if(value &gt;= mn) {\n        s.push(value);\n    } else if (value &lt; mn) {\n        s.push((2 * value)-mn);\n        mn = value;\n    }\n}\n\n\/\/ pop function\nvoid pop(){\n    if(s.top()&gt;=mn){\n        s.pop();\n    }else if(s.top()&lt;mn){\n        mn = (2*mn)-s.top();\n        s.pop();\n    }\n}\n\nlong long int top(){\n    if(!s.size())return -1;\n    else if(s.top()&gt;=mn)return s.top();\n    else return mn;\n}\n\nlong long int getmin(){\n    if(s.size()) return mn;\n    return 0;\n}\n\nint main(){\n    \/\/ call for push operation  with value 1\n    push(1);\n\n    \/\/ call for push operation with value 2\n    push(2);\n\n    \/\/ call for pop operation\n    pop();\n\n    \/\/ call for push operation with value 3\n    push(3);\n\n    \/\/ call for top opertion \n    int x = top();\n    \/\/ printing topmost element\n    cout&lt;&lt;x&lt;&lt;endl;   \/\/ output will be 3\n    \n\n    \/\/ call for minimum opertion\n    int y = getmin();  \n    \/\/ printing the minimum value\n    cout&lt;&lt;y&lt;&lt;endl; \/\/ output will be 1\n\n    return 0;\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Java Code<\/strong><\/h3>\n\n\n\n<p>Here is the Java code to solve Min Stack problem using one stack only:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-java&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Java&quot;,&quot;modeName&quot;:&quot;java&quot;}\">import java.util.Stack;\n\npublic class Main {\n    static Stack&lt;Long&gt; s = new Stack&lt;&gt;();\n    static long mn;\n\n    static void push(long value) {\n        if (s.size() == 0) {\n            s.push(value);\n            mn = value;\n        } else if (value &gt;= mn) {\n            s.push(value);\n        } else if (value &lt; mn) {\n            s.push((2 * value) - mn);\n            mn = value;\n        }\n    }\n\n    static void pop() {\n        if (s.peek() &gt;= mn) {\n            s.pop();\n        } else if (s.peek() &lt; mn) {\n            mn = (2 * mn) - s.peek();\n            s.pop();\n        }\n    }\n\n    static long top() {\n        if (s.size() == 0) return -1;\n        else if (s.peek() &gt;= mn) return s.peek();\n        else return mn;\n    }\n\n    static long getmin() {\n        if (s.size() != 0) return mn;\n        return 0;\n    }\n\n    public static void main(String[] args) {\n        \/\/ call for push operation  with value 1\n        push(1);\n\n        \/\/ call for push operation with value 2\n        push(2);\n\n        \/\/ call for pop operation\n        pop();\n\n        \/\/ call for push operation with value 3\n        push(3);\n\n        \/\/ call for top operation\n        long x = top();\n        \/\/ printing topmost element\n        System.out.println(x);   \/\/ output will be 3\n\n        \/\/ call for minimum operation\n        long y = getmin();\n        \/\/ printing the minimum value\n        System.out.println(y); \/\/ output will be 1\n    }\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Python Code<\/strong><\/h3>\n\n\n\n<p>Below is the Python code as well:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;python&quot;,&quot;mime&quot;:&quot;text\/x-python&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Python&quot;,&quot;modeName&quot;:&quot;python&quot;}\">s = []\nmn = 0\n\ndef push(value):\n    global mn\n    if len(s) == 0:\n        s.append(value)\n        mn = value\n    elif value &gt;= mn:\n        s.append(value)\n    elif value &lt; mn:\n        s.append((2 * value) - mn)\n        mn = value\n\ndef pop():\n    global mn\n    if s[-1] &gt;= mn:\n        s.pop()\n    elif s[-1] &lt; mn:\n        mn = (2 * mn) - s[-1]\n        s.pop()\n\ndef top():\n    if len(s) == 0:\n        return -1\n    elif s[-1] &gt;= mn:\n        return s[-1]\n    else:\n        return mn\n\ndef getmin():\n    if len(s) != 0:\n        return mn\n    return 0\n\n# call for push operation with value one.\npush(1)\n\n# call for push operation with value two.\npush(2)\n\n# call for pop operation\npop()\n\n# call for push operation with value three.\npush(3)\n\n# call for top operation\nx = top()\n# printing topmost element\nprint(x)   # output will be 3\n\n# call for minimum operation\ny = getmin()\n# printing the minimum value\nprint(y) # output will be 1<\/pre><\/div>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background has-link-color wp-elements-cf554874e15b17daaa9803799c035006\" style=\"background-color:#fedcba\"><code>3\n1<\/code><\/pre>\n\n\n\n<p>As we have seen, we are using just one stack to perform any operation, so the space complexity will not be O(n), and the time complexity remains O(1), as mentioned above.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>Min Stack problem from <a href=\"https:\/\/leetcode.com\/problems\/min-stack\/description\/\" target=\"_blank\" rel=\"noreferrer noopener nofollow\">leetcode<\/a> is often asked in many Data Structures coding interviews. We can also solve this problem using a Linked List instead of using a stack because a stack is composed of a linked list. Trying to solve this question using a <a href=\"https:\/\/favtutor.com\/blog-details\/linked-list-data-structure\">linked list<\/a> and finding its time and space complexity will yield the same results as in the one-stack approach. <\/p>\n","protected":false},"excerpt":{"rendered":"<p>Find out what the Min Stack  Problem is from the leetcode, with an example, and solve it using two stack or one stack only.<\/p>\n","protected":false},"author":14,"featured_media":1570,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-1565","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1565","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=1565"}],"version-history":[{"count":5,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1565\/revisions"}],"predecessor-version":[{"id":1647,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1565\/revisions\/1647"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/1570"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=1565"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=1565"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=1565"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}