{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreidxh7opl7bogclolbn72sttxu5wy2kszhh56rp2jnxijdwchkoaua",
    "uri": "at://did:plc:25rdn5elo5izoxrmtis34zuk/app.bsky.feed.post/3mpbzmsv7qp52"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreic4gimphqx57q6j5p5dgufw7l5xvb2eneheattce26neqeyyfiryq"
    },
    "mimeType": "image/webp",
    "size": 33444
  },
  "path": "/jaspreet_singh_86ae1740ac/min-stack-2pk5",
  "publishedAt": "2026-06-27T17:23:25.000Z",
  "site": "https://dev.to",
  "tags": [
    "algorithms",
    "interview",
    "java",
    "leetcode",
    "leetcode.com"
  ],
  "textContent": "\nleetcode.com\n\n\n##  Problem Statement\n\nDesign a stack that supports the following operations in **O(1)** time:\n\n\n\n    push(x)\n\n    pop()\n\n    top()\n\n    getMin()\n\n\n`getMin()` should always return the minimum element currently present in the stack.\n\n##  Brute Force Intuition\n\nIn an interview, you can explain it like this:\n\n> We can use a normal stack. Whenever `getMin()` is called, simply traverse the entire stack and find the minimum element.\n\nThis works, but every `getMin()` requires scanning all elements.\n\n###  Complexity\n\nOperation | Complexity\n---|---\npush | O(1)\npop | O(1)\ntop | O(1)\ngetMin | O(N)\n\n###  Brute Force Code\n\n\n    class MinStack {\n\n        Stack<Integer> st;\n\n        public MinStack() {\n            st = new Stack<>();\n        }\n\n        public void push(int val) {\n            st.push(val);\n        }\n\n        public void pop() {\n            st.pop();\n        }\n\n        public int top() {\n            return st.peek();\n        }\n\n        public int getMin() {\n\n            int min = Integer.MAX_VALUE;\n\n            for (int num : st) {\n                min = Math.min(min, num);\n            }\n\n            return min;\n        }\n    }\n\n\n##  Moving Towards the Optimal Approach\n\nThe problem is:\n\n\n\n    Finding Minimum\n\n\nInstead of searching every time,\n\nwhy not **store the minimum while inserting elements?**\n\nMaintain another stack that stores:\n\n\n\n    Current Minimum\n\n\nat every stage.\n\n##  Pattern Recognition\n\nWhenever you see:\n\n  * Stack\n  * Current Minimum / Maximum\n  * O(1) Query\n\n\n\nThink:\n\n**Two Stacks**\n\n##  Key Observation\n\nMain Stack:\n\n\n\n    5\n\n    2\n\n    8\n\n    1\n\n\nMin Stack:\n\n\n\n    5\n\n    2\n\n    2\n\n    1\n\n\nTop of Min Stack always stores:\n\n\n\n    Minimum Element\n\n\n##  Optimal Approach\n\n###  Push\n\nPush into main stack.\n\nIf:\n\n\n\n    Current element <= current minimum\n\n\nalso push into min stack.\n\n###  Pop\n\nIf popped element equals:\n\n\n\n    Minimum\n\n\nremove from min stack too.\n\n###  getMin()\n\nSimply return:\n\n\n\n    Top of Min Stack\n\n\n##  Optimal Java Solution\n\n\n    class MinStack {\n\n        Stack<Integer> stack;\n        Stack<Integer> minStack;\n\n        public MinStack() {\n\n            stack = new Stack<>();\n            minStack = new Stack<>();\n        }\n\n        public void push(int val) {\n\n            stack.push(val);\n\n            if (minStack.isEmpty()\n                || val <= minStack.peek()) {\n\n                minStack.push(val);\n            }\n        }\n\n        public void pop() {\n\n            if (stack.peek().equals(minStack.peek())) {\n                minStack.pop();\n            }\n\n            stack.pop();\n        }\n\n        public int top() {\n            return stack.peek();\n        }\n\n        public int getMin() {\n            return minStack.peek();\n        }\n    }\n\n\n##  Dry Run\n\n###  Operations\n\n\n    push(5)\n\n\nMain Stack:\n\n\n\n    5\n\n\nMin Stack:\n\n\n\n    5\n\n\n\n    push(2)\n\n\nMain:\n\n\n\n    2\n    5\n\n\nMin:\n\n\n\n    2\n    5\n\n\n\n    push(8)\n\n\nMain:\n\n\n\n    8\n    2\n    5\n\n\nMin:\n\n\n\n    2\n    5\n\n\nMinimum:\n\n\n\n    2\n\n\n\n    push(1)\n\n\nMain:\n\n\n\n    1\n    8\n    2\n    5\n\n\nMin:\n\n\n\n    1\n    2\n    5\n\n\nMinimum:\n\n\n\n    1\n\n\n\n    pop()\n\n\nRemove:\n\n\n\n    1\n\n\nMain:\n\n\n\n    8\n    2\n    5\n\n\nMin:\n\n\n\n    2\n    5\n\n\nMinimum:\n\n\n\n    2\n\n\n##  Why Two Stacks Work?\n\nEvery minimum value is stored separately.\n\nWhenever the minimum element is removed:\n\n\n\n    Remove it from Min Stack too.\n\n\nThus:\n\n\n\n    Top of Min Stack\n\n    =\n\n    Current Minimum\n\n\nwithout scanning the stack.\n\n##  Complexity Analysis\n\nOperation | Complexity\n---|---\nPush | O(1)\nPop | O(1)\nTop | O(1)\nGet Min | O(1)\n\n##  Follow-Up (Optimal Space)\n\nInstead of maintaining two stacks,\n\nwe can use:\n\n\n\n    One Stack\n\n    +\n\n    One Variable (min)\n\n\nusing an encoding technique.\n\nThis reduces auxiliary space while keeping all operations **O(1)**.\n\n##  Interview One-Liner\n\n> Maintain a second stack that stores the minimum element seen so far. The top of the second stack always represents the current minimum.\n\n##  Pattern Learned\n\n\n    Stack\n\n    +\n\n    Need Current Minimum\n\n    ↓\n\n    Extra Stack\n\n\n###  Similar Problems\n\n  * Min Stack\n  * Max Stack\n  * Stock Span\n  * Daily Temperatures\n  * Largest Rectangle in Histogram\n\n\n\n##  Memory Trick\n\nThink:\n\n\n\n    Push\n\n    ↓\n\n    Is New Minimum?\n\n    ↓\n\n    Yes\n\n    ↓\n\n    Push into Min Stack\n\n\n\n    Pop\n\n    ↓\n\n    Removing Minimum?\n\n    ↓\n\n    Pop from Min Stack\n\n\n###  Mental Model\n\n\n    Main Stack\n\n    Stores All Values\n\n    ↓\n\n    Min Stack\n\n    Stores Running Minimum\n\n\nWhenever you hear:\n\n> \"Design a stack supporting getMin() in O(1)\"\n\nyour brain should immediately think:\n\n**Two Stacks (Main Stack + Min Stack)**",
  "title": "Min Stack"
}