{"id":7691,"date":"2025-07-09T10:51:49","date_gmt":"2025-07-09T05:21:49","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=7691"},"modified":"2025-10-02T13:44:33","modified_gmt":"2025-10-02T08:14:33","slug":"min-stack","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/min-stack\/","title":{"rendered":"Min Stack"},"content":{"rendered":"\n<!-- MIN -->\n<!-- PrismJS for Syntax Highlighting -->\n<link\n    href=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/themes\/prism-tomorrow.min.css\"\n    rel=\"stylesheet\"\n\/>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/prism.min.js\"><\/script>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/plugins\/autoloader\/prism-autoloader.min.js\"><\/script>\n\n<style>\n.wp_blog_theme {\n  --primary: #E58C32;\n  --secondary: #030302;\n  --light-bg: #fef9f4;\n  --text-dark: #2d2d2d;\n  --tab-radius: 12px;\n  --shadow: 0 4px 12px rgba(0, 0, 0, 0.08);\n  --code-bg: #001f3f;\n  --code-text: #d4f1ff;\n}\n\n.wp_blog_container {\n  font-family: 'Segoe UI', sans-serif;\n  background: var(--light-bg);\n  margin: 0;\n  padding: 0;\n  color: var(--text-dark);\n}\n\n\/* Heading *\/\n.wp_blog_main-heading {\n  text-align: center;\n  font-size: 2.4rem;\n  color: var(--primary);\n  margin-top: 2.5rem;\n  font-weight: bold;\n}\n\n\/* Explanation Card *\/\n.wp_blog_explanation,\n.wp_blog_code-tabs-container {\n  max-width: 940px;\n  margin: 2rem auto;\n  padding: 2rem;\n  background: white;\n  border-radius: var(--tab-radius);\n  box-shadow: var(--shadow);\n}\n\n\/* Text and Visuals *\/\n.wp_blog_explanation h2 {\n  font-size: 1.4rem;\n  color: var(--primary);\n  margin-bottom: 0.5rem;\n}\n\n.wp_blog_explanation p,\n.wp_blog_explanation li {\n  font-size: 1.05rem;\n  line-height: 1.7;\n  margin: 0.5rem 0;\n}\n\n.wp_blog_explanation code {\n  background: #fef9f4;   \/* light bg instead of dark blue *\/\n  color: #E58C32;        \/* brand orange *\/\n  padding: 3px 6px;\n  border-radius: 4px;\n  font-family: 'Courier New', monospace;\n  font-weight: 600;      \/* optional, makes it pop *\/\n}\n\n.wp_blog_explanation img {\n  max-width: 100%;\n  border-radius: var(--tab-radius);\n  margin-top: 1rem;\n  box-shadow: 0 2px 12px rgba(0, 0, 0, 0.06);\n}\n\n\/* Tab Buttons *\/\n.wp_blog_code-tabs-header {\n  display: flex;\n  flex-wrap: wrap;\n  gap: 0.5rem;\n  margin-bottom: 1rem;\n}\n\n.wp_blog_code-tab-button {\n  padding: 0.6rem 1.2rem;\n  border: 1px solid var(--primary);\n  background: white;\n  color: var(--primary);\n  border-radius: 50px;\n  font-weight: 600;\n  cursor: pointer;\n  transition: all 0.3s ease;\n}\n\n.wp_blog_code-tab-button:hover {\n  background: var(--secondary);\n}\n\n.wp_blog_code-tab-button.active {\n  background: var(--primary);\n  color: white;\n}\n\n\/* Code Content *\/\n.wp_blog_code-tab-content {\n  display: none;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n}\n\n.wp_blog_code-tab-content.active {\n  display: block;\n}\n\n.wp_blog_code-tab-content pre {\n  margin: 0;\n  padding: 1.5rem;\n  font-size: 1rem;\n  overflow-x: auto;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n  color: var(--code-text);\n}\n\n\/* Dark mode variables *\/\n.wp_blog_theme.dark-mode {\n  --light-bg: #121212;\n  --text-dark: #f5f5f5;\n  --shadow: 0 4px 12px rgba(255, 255, 255, 0.08);\n  --code-bg: #1e1e1e;\n  --code-text: #c5f0ff;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_explanation {\n  background: #1e1e1e;\n}\n\n\/* Dark mode code highlight *\/\n.wp_blog_theme.dark-mode .wp_blog_explanation code {\n  background: #333;\n  color: #ffd27f;\n}\n\n.wp_blog_theme {\n  position: relative; \/* makes it the reference for absolute children *\/\n}\n\n.wp_blog_toggle-btn {\n  position: absolute;\n  top: 1rem;\n  right: 1rem;\n  z-index: 9999;\n  padding: 0.5rem 0.8rem;\n  border-radius: 10%;\n  background: var(--primary);\n  color: white;\n  font-weight: bold;\n  cursor: pointer;\n  border: none;\n  box-shadow: var(--shadow);\n  transition: background 0.3s, transform 0.2s;\n}\n\n.wp_blog_toggle-btn:hover {\n  background: #cc772e;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_code-tabs-container {\n  background: #1e1e1e;\n}\n<\/style>\n<div class=\"wp_blog_container wp_blog_theme\">\n            <button id=\"blogNotesThemeToggle\" class=\"wp_blog_toggle-btn\">\ud83c\udf19<\/button>\n<h1 class=\"wp_blog_main-heading\"><\/h1>\n\n<div class=\"wp_blog_explanation\">\n    <h2>Problem Statement:<\/h2>\n    <p>\n       Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.\n    <\/p>\n\n    <p>Implement the <code>MinStack<\/code> class:<\/p>\n    <p>\n       <ul>\n        <li><code>MinStack()<\/code>initializes the stack object.<\/li>\n        <li><code>void push(int val)<\/code>pushes the element <code>val<\/code> onto the stack.<\/li>\n        <li><code>void pop()<\/code>removes the element on the top of the stack.<\/li>\n        <li><code>int top()<\/code>gets the top element of the stack.<\/li>\n        <li><code>int getMin()<\/code>retrieves the minimum element in the stack.<\/li>\n    <\/ul>\n    <\/p>\n\n    <p>You must implement a solution with <code>O(1)<\/code> time complexity for each function.<\/p>\n\n    <h2>Examples:<\/h2>\n    <p><strong>Example 1:<\/strong><\/p>\n    <p><strong>Input:<\/strong><\/p>\n        <p>[&#8220;MinStack&#8221;,&#8221;push&#8221;,&#8221;push&#8221;,&#8221;push&#8221;,&#8221;getMin&#8221;,&#8221;pop&#8221;,&#8221;top&#8221;,&#8221;getMin&#8221;] <\/br>\n                              [[],[-2],[0],[-3],[],[],[],[]]<\/p>\n    <p><strong>Output:<\/strong><code>[null,null,null,null,-3,null,0,-2]<\/code><\/p>\n\n    <p><strong>Explanation<\/strong><\/p>\n        <pre>\n        MinStack minStack = new MinStack();\n        minStack.push(-2);\n        minStack.push(0);\n        minStack.push(-3);\n        minStack.getMin(); \/\/ return -3\n        minStack.pop();\n        minStack.top();    \/\/ return 0\n        minStack.getMin(); \/\/ return -2\n        <\/pre>\n    <h2>Constraints:<\/h2>\n    <ul>\n        <li><code>-2<sup>31<\/sup> <= val <= 2<sup>31<\/sup> - 1<\/code><\/li>\n        <li>Methods <code>pop<\/code>, <code>top<\/code> and <code>getMin<\/code> operations will always be called on <strong>non-empty<\/strong> stacks.<\/li>\n        <li>At most <code>3 * 10<sup>4<\/sup><\/code> calls will be made to <code>push<\/code>, <code>pop<\/code>, <code>top<\/code>, and <code>getMin<\/code><\/li>\n    <\/ul>\n\n    <h2>Approach:<\/h2>\n    <ul>\n        <li>\n            Initialize stack, Use an array s to store pairs <code>[value, currentMin]<\/code>.\n        <\/li>\n\n        <li>\n          push(val) \n        <ul>\n            <li>If stack is empty, push <code>[val, val]<\/code>.<\/li>\n            <li>Else, push <code>[val, min(val, top\u2019s min)]<\/code>.<\/li>\n        <\/ul>\n        <\/li>\n\n        <li>pop(): Remove the top element using <code>pop()<\/code>.<\/li>\n        <li>top(): Return the top value: <code>s[s.length - 1][0]<\/code>.<\/li>\n        <li>getMin(): Return the current minimum: <code>s[s.length - 1][1]<\/code>.<\/li>\n    <\/ul>\n\n    <h2>Visualisation:<\/h2>\n    <img decoding=\"async\"\n        src=\"https:\/\/namastedev.com\/blog\/wp-content\/uploads\/2025\/07\/Screenshot-2025-07-09-at-10.43.32\u202fAM.png\"\n        alt=\"stack\"\n    \/>\n                <h2>Time Complexity:<\/h2>\n                <li>\n                  <p>All operations: <strong>O(1)<\/strong><\/p>\n                <\/li> \n                <h2>Space Complexity:<\/h2>\n                <li>\n                  <p><strong>Space Complexity = O(n)<\/strong> \n                <\/p>\n                <\/li>\n\n<h2>Dry Run:<\/h2> <div style=\"background: var(--light-bg); border-left: 4px solid var(--primary); padding: 1rem; border-radius: var(--tab-radius); margin: 1rem 0; color: var(--text-dark);\"> <p><strong>Input:<\/strong><\/p> <pre style=\"white-space: pre-wrap; background: var(--code-bg); padding: 1rem; border-radius: 8px; overflow-x: auto; color: var(--code-text);\"> Operations: push(3) push(5) push(2) push(1) getMin() pop() getMin() top() <\/pre> <p><strong>State Transitions:<\/strong><\/p> <pre style=\"white-space: pre-wrap; background: var(--code-bg); padding: 1rem; border-radius: 8px; overflow-x: auto; color: var(--code-text);\"> After push(3): s = [[3, 3]]\nAfter push(5):\nmin(5, 3) = 3 \u2192 push [5, 3]\ns = [[3, 3], [5, 3]]\nAfter push(2):\nmin(2, 3) = 2 \u2192 push [2, 2]\ns = [[3, 3], [5, 3], [2, 2]]\nAfter push(1):\nmin(1, 2) = 1 \u2192 push [1, 1]\ns = [[3, 3], [5, 3], [2, 2], [1, 1]]\ngetMin():\nTop element = [1, 1] \u2192 min = <strong>1<\/strong>\npop():\nRemove top element \u2192 [1, 1]\ns = [[3, 3], [5, 3], [2, 2]]\ngetMin():\nTop element = [2, 2] \u2192 min = <strong>2<\/strong>\ntop():\nTop element = [2, 2] \u2192 value = <strong>2<\/strong>\n<\/pre>\n<p><strong>Final State:<\/strong> <code>s = [[3, 3], [5, 3], [2, 2]]<\/code> (top to bottom: last element is top)<\/p> <\/div>\n\n<\/div>\n\n<div class=\"wp_blog_code-tabs-container\">\n    <div class=\"wp_blog_code-tabs-header\">\n        <button class=\"wp_blog_code-tab-button active\" data-lang=\"js\">\n            JavaScript\n        <\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"py\">Python<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"java\">Java<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"cpp\">C++<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"c\">C<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"cs\">C#<\/button>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content active\" data-lang=\"js\">\n<pre><code class=\"language-javascript\">\nvar MinStack = function() {\n    this.s = [];\n};\nMinStack.prototype.push = function(val) {\n    if(this.s.length === 0){\n        this.s.push([val, val]);\n    } else {\n        let minVal = Math.min(val, this.s[this.s.length - 1][1]);\n        this.s.push([val, minVal]);\n    }\n};\nMinStack.prototype.pop = function() {\n    this.s.pop();\n};\nMinStack.prototype.top = function() {\n    return this.s[this.s.length-1][0];\n};\nMinStack.prototype.getMin = function() {\n    return this.s[this.s.length-1][1];\n};\n<\/code><\/pre>\n<\/div>\n\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"py\">\n        <pre><code class=\"language-python\">\nclass MinStack:\n  def __init__(self):\n    self.s = []\n  def push(self, val: int) -> None:\n    if not self.s:\n     self.s.append((val, val))\n    else:\n     minVal = min(val, self.s[-1][1])\n     self.s.append((val, minVal))\n  def pop(self) -> None:\n     self.s.pop()\n  def top(self) -> int:\n     return self.s[-1][0]\n  def getMin(self) -> int:\n     return self.s[-1][1]\n    <\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"java\">\n        <pre><code class=\"language-java\">\nimport java.util.*;\nclass MinStack {\n    List<int[]> s;\n    public MinStack() {\n        s = new ArrayList<>();\n    }\n    public void push(int val) {\n        if (s.isEmpty()) {\n            s.add(new int[]{val, val});\n        } else {\n            int minVal = Math.min(val, s.get(s.size() - 1)[1]);\n            s.add(new int[]{val, minVal});\n        }\n    }\n    public void pop() {\n        s.remove(s.size() - 1);\n    }\n    public int top() {\n        return s.get(s.size() - 1)[0];\n    }\n    public int getMin() {\n        return s.get(s.size() - 1)[1];\n    }\n}\n <\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"cpp\">\n        <pre><code class=\"language-cpp\">\nclass MinStack {\npublic:\n    vector<pair<int, int>> s;\n    void push(int val) {\n        if (s.empty()) {\n            s.push_back({val, val});\n        } else {\n            int minVal = min(val, s.back().second);\n            s.push_back({val, minVal});\n        }\n    }\n    void pop() {\n        s.pop_back();\n    }\n    int top() {\n        return s.back().first;\n    }\n    int getMin() {\n        return s.back().second;\n    }\n};\n<\/code><\/pre>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"c\">\n        <pre><code class=\"language-c\">\n#include &lt;stdio.h&gt;\n#include &lt;stdlib.h&gt;\n#include &lt;limits.h&gt;\ntypedef struct {\n    int val;\n    int min;\n} StackNode;\ntypedef struct {\n    StackNode* arr;\n    int top;\n    int capacity;\n} MinStack;\nMinStack* minStackCreate() {\n    MinStack* stack = (MinStack*)malloc(sizeof(MinStack));\n    stack->capacity = 1000;\n    stack->top = -1;\n    stack->arr = (StackNode*)malloc(sizeof(StackNode) * stack->capacity);\n    return stack;\n}\nvoid minStackPush(MinStack* stack, int val) {\n    int minVal = val;\n    if (stack->top >= 0 && stack->arr[stack->top].min < val) {\n        minVal = stack->arr[stack->top].min;\n    }\n    stack->arr[++stack->top] = (StackNode){val, minVal};\n}\nvoid minStackPop(MinStack* stack) {\n    if (stack->top >= 0) {\n        stack->top--;\n    }\n}\nint minStackTop(MinStack* stack) {\n    return stack->arr[stack->top].val;\n}\nint minStackGetMin(MinStack* stack) {\n    return stack->arr[stack->top].min;\n}\n<\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"cs\">\n        <pre><code class=\"language-csharp\">\nusing System;\nusing System.Collections.Generic;\npublic class MinStack {\n    private List<(int val, int min)> s;\n    public MinStack() {\n        s = new List<(int, int)>();\n    }\n    public void Push(int val) {\n        if (s.Count == 0) {\n            s.Add((val, val));\n        } else {\n            int minVal = Math.Min(val, s[s.Count - 1].min);\n            s.Add((val, minVal));\n        }\n    }\n    public void Pop() {\n        s.RemoveAt(s.Count - 1);\n    }\n    public int Top() {\n        return s[s.Count - 1].val;\n    }\n    public int GetMin() {\n        return s[s.Count - 1].min;\n    }\n}\n  <\/code><\/pre>\n    <\/div>\n<\/div>\n<\/div>\n<script>\ndocument.addEventListener(\"DOMContentLoaded\", () => {\n  const buttons = document.querySelectorAll(\".wp_blog_code-tab-button\");\n  const contents = document.querySelectorAll(\".wp_blog_code-tab-content\");\n\n  buttons.forEach((button) => {\n    button.addEventListener(\"click\", () => {\n      const lang = button.getAttribute(\"data-lang\");\n\n      buttons.forEach((btn) => btn.classList.remove(\"active\"));\n      contents.forEach((content) => content.classList.remove(\"active\"));\n\n      button.classList.add(\"active\");\n      document\n        .querySelector(`.wp_blog_code-tab-content[data-lang=\"${lang}\"]`)\n        .classList.add(\"active\");\n    });\n  });\n\n  const themeToggle = document.getElementById(\"blogNotesThemeToggle\");\n  const themeContainer = document.querySelector(\".wp_blog_theme\");\n\n  themeToggle.addEventListener(\"click\", () => {\n    themeContainer.classList.toggle(\"dark-mode\");\n    themeToggle.textContent =\n      themeContainer.classList.contains(\"dark-mode\") ? \"\u2600\ufe0f\" : \"\ud83c\udf19\";\n  });\n});\n<\/script>\n","protected":false},"excerpt":{"rendered":"<p>\ud83c\udf19 Problem Statement: Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class: MinStack()initializes the stack object. void push(int val)pushes the element val onto the stack. void pop()removes the element on the top of the stack. int top()gets the top element of the stack. int<\/p>\n","protected":false},"author":108,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[260,176,175,211,811,810,174,172,173],"tags":[],"class_list":["post-7691","post","type-post","status-publish","format-standard","category-c-c-plus-plus","category-csharp","category-cplusplus","category-data-structures","category-data-structures-and-algorithms","category-dsa","category-java","category-javascript","category-python"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/7691","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/users\/108"}],"replies":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/comments?post=7691"}],"version-history":[{"count":5,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/7691\/revisions"}],"predecessor-version":[{"id":10212,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/7691\/revisions\/10212"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=7691"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=7691"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=7691"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}