CSInterviewing
Problems
Register
Login
Problems
Register
Login
menu
Min Stack (Stack with getMax)
stack
design
# Min Stack (Stack with getMax) ## Difficulty Medium ## Tags `stack`, `design` ## Problem Statement Design a stack that supports the following operations in O(1) time complexity: - `push(x)`: Push element x onto the stack. - `pop()`: Remove the element on top of the stack. - `top()`: Get the top element. - `get_min()`: Retrieve the minimum element in the stack. ## Constraints - -2³¹ ≤ val ≤ 2³¹ - 1 - Methods `pop`, `top`, and `get_min` will always be called on non-empty stacks. - At most 3 × 10⁴ calls to each method. ## Signatures ### Python ```python class MinStack: def push(self, val: int) -> None: pass def pop(self) -> None: pass def top(self) -> int: pass def get_min(self) -> int: pass ``` ### Java ```java public class MinStack { // Implement methods here } ``` ### Csharp ```csharp public class MinStack { // Implement methods here } ``` ### Cpp ```cpp class MinStack { public: // Implement methods here }; ``` ### C ```c void __init__() { } ``` ### Ruby ```ruby def __init__() end ``` ### Perl ```perl sub __init__ { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def __init__(): Unit = { } } ``` ### Haskell ```haskell __init__ :: ... -> ... __init__ args = undefined ``` ### Clojure ```clojure (defn __init__ [] ) ``` ### Scheme ```scheme (define (__init__ ) ) ``` ## Examples ### Example 1 **Input:** ``` stack = MinStack() stack.push(-2) stack.push(0) stack.push(-3) stack.get_min() # returns -3 stack.pop() stack.top() # returns 0 stack.get_min() # returns -2 ``` **Output:** ``` -3, 0, -2 ``` ### Example 2 **Input:** ``` stack = MinStack() stack.push(5) stack.push(3) stack.push(7) stack.get_min() # returns 3 stack.push(1) stack.get_min() # returns 1 stack.pop() stack.get_min() # returns 3 ``` ## Hints 1. Use two stacks: one for values, one for tracking minimums. 2. When pushing x, push to the main stack. If min_stack is empty or x ≤ min_stack.top(), also push to min_stack. 3. When popping, if popped value equals min_stack.top(), also pop from min_stack. 4. `get_min()` returns min_stack.top(). Alternative: Store pairs of (value, current_min) in a single stack.
Login required
Please log in to view the solution editor and submit code.
Login
Register