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.

Please log in to view the solution editor and submit code.