{"id":853,"date":"2025-08-06T11:47:09","date_gmt":"2025-08-06T06:17:09","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=853"},"modified":"2025-08-06T11:47:11","modified_gmt":"2025-08-06T06:17:11","slug":"min-stack","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/min-stack\/","title":{"rendered":"Min Stack | Leetcode 155 | Optimal Solution in Python"},"content":{"rendered":"\n<p>If you want to master stack-related challenges and ace your coding interviews, understanding how to implement a&nbsp;<strong>Min Stack<\/strong>&nbsp;is crucial. This classic problem not only tests your ability to design efficient data structures but also sharpens your skills in managing auxiliary information within a stack to optimize queries.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/min-stack\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<p>In this comprehensive guide, we\u2019ll look at the problem statement, walk through a carefully explained solution, and break down the time and space complexities, all presented with clarity to help beginners and experts alike.<\/p>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-696bb715-b6c3-4d2a-9f4b-a2a5d014fcb2\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"true\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/min-stack\/#0-problem-statement\" style=\"\">Problem Statement<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/min-stack\/#1-why-is-this-challenging\" style=\"\">Why Is This Challenging?<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/min-stack\/#2-intuition-and-approach-storing-current-minimums-alongside-each-element\" style=\"\">Intuition and Approach: Storing Current Minimums Alongside Each Element<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/min-stack\/#3-detailed-code-implementation\" style=\"\">Detailed Code Implementation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/min-stack\/#4-explanation-of-each-operation\" style=\"\">Explanation of Each Operation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/min-stack\/#5-example-breakdown\" style=\"\">Example Breakdown<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/min-stack\/#6-time-and-space-complexity-analysis\" style=\"\">Time and Space Complexity Analysis<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/min-stack\/#7-real-world-applications\" style=\"\">Real-World Applications<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/min-stack\/#8-conclusion\" style=\"\">Conclusion<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<h2 class=\"wp-block-heading\" id=\"0-problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Design a stack that supports four operations, each in constant time (<code>O(1)<\/code>):<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong><code>push(val)<\/code><\/strong>: Pushes the integer\u00a0<code>val<\/code>\u00a0onto the stack.<\/li>\n\n\n\n<li><strong><code>pop()<\/code><\/strong>: Removes the element on the top of the stack.<\/li>\n\n\n\n<li><strong><code>top()<\/code><\/strong>: Retrieves the top element of the stack without removing it.<\/li>\n\n\n\n<li><strong><code>getMin()<\/code><\/strong>: Retrieves the minimum element in the entire stack at any point.<\/li>\n<\/ul>\n\n\n\n<p>Your stack must efficiently keep track of the minimum element without the need to scan through the entire stack every time you call&nbsp;<code>getMin()<\/code>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"1-why-is-this-challenging\">Why Is This Challenging?<\/h2>\n\n\n\n<p>A usual stack supports push, pop, and top in constant time. But tracking the minimum element needs extra thought. The naive approach is this:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>On each\u00a0<code>getMin()<\/code>, scan through the entire stack to find the minimum element, which costs\u00a0<code>O(n)<\/code>\u00a0time.<\/li>\n\n\n\n<li>This is inefficient and not acceptable for time-critical use cases or interview-level coding problems.<\/li>\n<\/ul>\n\n\n\n<p>Our goal is to maintain all operations in&nbsp;<code>O(1)<\/code>&nbsp;time, including&nbsp;<code>getMin()<\/code>, which requires a specialized design.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"2-intuition-and-approach-storing-current-minimums-alongside-each-element\">Intuition and Approach: Storing Current Minimums Alongside Each Element<\/h2>\n\n\n\n<p>The key insight is&nbsp;<strong>to store, alongside every pushed element, the minimum element in the stack up to that point.<\/strong>&nbsp;This way, every element on the stack knows what the current minimum is when it was pushed.<\/p>\n\n\n\n<p>How does this work?<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>When the stack is empty and we push the first element, the minimum is the element itself, so we store\u00a0<code>(value, value)<\/code>.<\/li>\n\n\n\n<li>When pushing a new element, compare it to the minimum stored with the stack\u2019s top element.<\/li>\n\n\n\n<li>The new minimum is the smaller of:\n<ul class=\"wp-block-list\">\n<li>The new element\u2019s value<\/li>\n\n\n\n<li>The current minimum<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Push the pair\u00a0<code>(new value, new minimum)<\/code>\u00a0onto the stack.<\/li>\n<\/ol>\n\n\n\n<p>Thus:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>getMin()<\/code>\u00a0simply returns the minimum stored with the top element.<\/li>\n\n\n\n<li><code>top()<\/code>\u00a0returns the value part of the top element.<\/li>\n\n\n\n<li><code>pop()<\/code>\u00a0removes the top element (and, implicitly, the minimum stored with it).<\/li>\n<\/ul>\n\n\n\n<p>This design ensures constant-time retrieval of the minimum, with no extra traversal.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"3-detailed-code-implementation\">Detailed Code Implementation<\/h2>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class MinStack:\n    def __init__(self):\n        # Stack holds pairs: [element_value, current_min]\n        self.stack = []\n\n    def push(self, val: int) -&gt; None:\n        if len(self.stack) == 0:\n            # If stack empty, min is val itself\n            self.stack.append([val, val])\n        else:\n            # Current minimum is top element's min value\n            current_min = self.stack[-1][1]\n            # New minimum is smaller of val and current min\n            new_min = min(current_min, val)\n            self.stack.append([val, new_min])\n\n    def pop(self) -&gt; None:\n        if self.stack:\n            self.stack.pop()\n\n    def top(self) -&gt; int:\n        if not self.stack:\n            return None  # Or raise exception as per requirement\n        # Return the value part of the top element\n        return self.stack[-1][0]\n\n    def getMin(self) -&gt; int:\n        if not self.stack:\n            return None  # Or raise exception as per requirement\n        # Return the min part of the top element\n        return self.stack[-1][1]\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">MinStack<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">__init__<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Stack holds pairs: [element_value, current_min]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.stack = []<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">push<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">val<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.stack) == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># If stack empty, min is val itself<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.stack.append([val, val])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Current minimum is top element&#39;s min value<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            current_min = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.stack[-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># New minimum is smaller of val and current min<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            new_min = <\/span><span style=\"color: #DCDCAA\">min<\/span><span style=\"color: #D4D4D4\">(current_min, val)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.stack.append([val, new_min])<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">pop<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.stack:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.stack.pop()<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">top<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.stack:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Or raise exception as per requirement<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Return the value part of the top element<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.stack[-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">getMin<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.stack:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># Or raise exception as per requirement<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Return the min part of the top element<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.stack[-<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">][<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"4-explanation-of-each-operation\">Explanation of Each Operation<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong><code>push(val)<\/code><\/strong><br>Adds an element paired with the minimum value so far. It compares the value to the current minimum and decides which minimum to record for this level.<\/li>\n\n\n\n<li><strong><code>pop()<\/code><\/strong><br>Removes the topmost pair. Both the value and the minimum associated with that state get removed, revealing the previous minimum beneath.<\/li>\n\n\n\n<li><strong><code>top()<\/code><\/strong><br>Returns the latest pushed value without removing it.<\/li>\n\n\n\n<li><strong><code>getMin()<\/code><\/strong><br>Returns the minimum element among all values currently in the stack instantly, thanks to the stored min information.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"5-example-breakdown\">Example Breakdown<\/h2>\n\n\n\n<p>Consider a sequence of operations:<\/p>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(1 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"minStack = MinStack()\nminStack.push(3)\nminStack.push(5)\nminStack.push(2)\nminStack.push(1)\nminStack.push(4)\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #D4D4D4\">minStack = MinStack()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">minStack.push(<\/span><span style=\"color: #B5CEA8\">3<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">minStack.push(<\/span><span style=\"color: #B5CEA8\">5<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">minStack.push(<\/span><span style=\"color: #B5CEA8\">2<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">minStack.push(<\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">minStack.push(<\/span><span style=\"color: #B5CEA8\">4<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>Stack content (value, min):<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>[ (3,3) ]<\/li>\n\n\n\n<li>[ (3,3), (5,3) ]<\/li>\n\n\n\n<li>[ (3,3), (5,3), (2,2) ]<\/li>\n\n\n\n<li>[ (3,3), (5,3), (2,2), (1,1) ]<\/li>\n\n\n\n<li>[ (3,3), (5,3), (2,2), (1,1), (4,1) ]<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><code>getMin()<\/code>&nbsp;\u2192 returns&nbsp;<code>1<\/code>&nbsp;(top element min)<\/li>\n\n\n\n<li><code>pop()<\/code>&nbsp;\u2192 removes&nbsp;<code>(4,1)<\/code><\/li>\n\n\n\n<li><code>getMin()<\/code>&nbsp;\u2192 still&nbsp;<code>1<\/code>&nbsp;(from&nbsp;<code>(1,1)<\/code>)<\/li>\n\n\n\n<li><code>pop()<\/code>&nbsp;\u2192 removes&nbsp;<code>(1,1)<\/code><\/li>\n\n\n\n<li><code>getMin()<\/code>&nbsp;\u2192&nbsp;<code>2<\/code>&nbsp;(from&nbsp;<code>(2,2)<\/code>)<\/li>\n\n\n\n<li><code>top()<\/code>&nbsp;\u2192&nbsp;<code>2<\/code>&nbsp;(value of the top)<\/li>\n<\/ol>\n\n\n\n<p>This shows how the stored minimum changes dynamically with push and pop.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"6-time-and-space-complexity-analysis\">Time and Space Complexity Analysis<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Operation<\/th><th>Complexity<\/th><th>Explanation<\/th><\/tr><\/thead><tbody><tr><td>push<\/td><td>O(1)<\/td><td>Just comparing and pushing a pair<\/td><\/tr><tr><td>pop<\/td><td>O(1)<\/td><td>Popping the top pair from the stack<\/td><\/tr><tr><td>top<\/td><td>O(1)<\/td><td>Accessing the last element<\/td><\/tr><tr><td>getMin<\/td><td>O(1)<\/td><td>Reading stored minimum from top element<\/td><\/tr><tr><td>Space<\/td><td>O(n)<\/td><td>Each element stores additional minimum data<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>This makes the stack scalable and performant even for large data sets or time-sensitive applications.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"7-real-world-applications\">Real-World Applications<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Tracking minimum in dynamic datasets:<\/strong>\u00a0Useful in algorithms that need quick min queries during data processing.<\/li>\n\n\n\n<li><strong>Undo operations:<\/strong>\u00a0Where you want to quickly recall states with min\/max information.<\/li>\n\n\n\n<li><strong>Financial or gaming apps:<\/strong>\u00a0Where real-time minimums or maximums influence plays or strategy.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"8-conclusion\">Conclusion<\/h2>\n\n\n\n<p>The&nbsp;<strong>Min Stack<\/strong>&nbsp;problem perfectly demonstrates how to augment a common data structure with auxiliary information to achieve efficient queries. By storing the current minimum with each pushed element, all operations, including minimum retrieval, remain constant-time. This technique is both elegant and practical for interview success and real-world system design.<\/p>\n\n\n\n<p>For practice, try similar stack problems like&nbsp;<strong>Max Stack<\/strong>, or variations with constant-time median retrieval to deepen your understanding.<\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>If you want to master stack-related challenges and ace your coding interviews, understanding how to implement a&nbsp;Min Stack&nbsp;is crucial. This classic problem not only tests your ability to design efficient data structures but also sharpens your skills in managing auxiliary information within a stack to optimize queries. Here&#8217;s the [Problem Link] to begin with. In<\/p>\n","protected":false},"author":1,"featured_media":854,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[19,37],"class_list":{"0":"post-853","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-intermediate","9":"tag-medium","10":"tag-stack-and-queues"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/08\/min-stack-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/853","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=853"}],"version-history":[{"count":1,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/853\/revisions"}],"predecessor-version":[{"id":855,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/853\/revisions\/855"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/854"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=853"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=853"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=853"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}