Solved problem 155 : Min Stack

racoelhosilva · racoelhosilva · commit 7278291d67fa · 2024-03-01T14:57:49.000Z
diff --git a/README.md b/README.md
@@ -16,7 +16,7 @@
 
 ### Problems Solved
 
-| Total | 60 |
+| Total | 61 |
 |:---:|:---:|
 
 #### Search By Topic
@@ -38,7 +38,7 @@
 | Math & Geometry | 4 |
 | Priority Queue | 3 |
 | Sliding Window | 2 |
-| Stack | 3 |
+| Stack | 4 |
 | Tries | 0 |
 | Two Pointers | 6 |
 
@@ -47,7 +47,7 @@
 | Difficulty | Number |
 |:---|---:|
 | Easy | 48 |
-| Medium | 12 |
+| Medium | 13 |
 | Hard | 0 |
 
 ## Milestones
diff --git a/Stack/Medium/155_MinStack.cpp b/Stack/Medium/155_MinStack.cpp
@@ -0,0 +1,82 @@
+/* 
+ * Problem: 155 
+ * Name: Min Stack
+ * Difficulty: Medium
+ * Topic: Stack
+ * Link: https://leetcode.com/problems/min-stack/
+ */
+ 
+#include <bits/stdc++.h>
+using namespace std;
+
+//      Stack-Pair Approach
+// Stack will store pairs of {elements, relative-mininums}
+// push: O(1)
+// pop: O(1)
+class MinStack {
+private:
+    stack<pair<int,int>> stack;
+
+public:
+    MinStack() {}
+    
+    void push(int val) {
+        if (stack.empty()){
+            stack.push({val,val});
+        }
+        else {
+            stack.push({val, min(stack.top().second, val)});
+        }
+    }
+    
+    void pop() {
+        stack.pop();
+    }
+    
+    int top() {
+        return stack.top().first;
+    }
+    
+    int getMin() {
+        return stack.top().second;
+    }
+};
+
+//      Two-Stack Approach
+// main stack will store all elements like a regular stack
+// mins stack will only store "relative" minimum values
+// push: O(1)
+// pop: O(1)
+class MinStack {
+private:
+    stack<int> main;
+    stack<int> mins;
+
+public:
+    MinStack() {}
+    
+    void push(int val) {
+        main.push(val);
+        if (mins.empty()){
+            mins.push(val);
+        }
+        else if (val <= mins.top()){
+            mins.push(val);
+        }
+    }
+    
+    void pop() {
+        if (main.top() == mins.top()){
+            mins.pop();
+        }
+        main.pop();
+    }
+    
+    int top() {
+        return main.top();
+    }
+    
+    int getMin() {
+        return mins.top();
+    }
+};
