# The Min Tracker

> The stack remembers the best it ever saw.

Canonical URL: <https://datadriven.io/problems/the_min_tracker>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Implement a class MinStack supporting push(x), pop(), and get_min(). All three operations must run in O(1) time. get_min returns the current minimum element in the stack without removing it. (The visible test harness passes operation names and arguments as parallel lists and expects a parallel list of return values: None for push/pop, the min value for get_min.)

## Worked solution and explanation

### Why this problem exists in real interviews

This tests the **auxiliary stack pattern** for maintaining invariants alongside a primary data structure. It checks whether candidates can achieve O(1) for all three operations by trading space for time.

> **Trick to Solving**
>
> Maintain a parallel stack where each entry records the minimum value at the corresponding depth. When you push a value, push the smaller of the new value and the current minimum onto the min stack. When you pop, pop both stacks.

---

### Break down the requirements

#### Step 1: Use two stacks: main and min-tracking

The main stack stores values normally. The min stack mirrors it, where each entry is the minimum of all values from the bottom up to that position.

#### Step 2: Push updates both stacks

Push the value onto the main stack. Push `min(value, current_min)` onto the min stack.

#### Step 3: Pop removes from both

Pop from both stacks simultaneously to keep them synchronized.

#### Step 4: get_min reads the min stack top

The minimum for the current stack state is always at the top of the min stack.

---

### The solution

**Dual stack with synchronized min tracking**

```python
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
    def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
        else:
            self.min_stack.append(self.min_stack[-1])
    def pop(self):
        self.min_stack.pop()
        return self.stack.pop()
    def get_min(self):
        return self.min_stack[-1]
```

> **Time and Space Complexity**
>
> **Time:** O(1) for push, pop, and get_min. All are single-operation stack accesses.
> 
> **Space:** O(n) for the auxiliary min stack, doubling total memory usage.

> **Interviewers Watch For**
>
> Using `<=` when checking whether to update the min stack. If you use `<`, pushing the same minimum value twice will break the pop logic when the first copy is removed.

> **Common Pitfall**
>
> Trying to optimize the min stack to only push when a new minimum appears. This works but requires careful handling of duplicates during pop, making the code error-prone.

---

## Common follow-up questions

- Can you implement this with O(1) extra space instead of a full auxiliary stack? _(Tests encoding the min information in the values themselves using a difference-based approach.)_
- What if you also needed get_max in O(1)? _(Tests adding a third stack for maximum tracking.)_
- How would you make this thread-safe? _(Tests lock granularity and atomic operations on stack pairs.)_
- What happens if pop is called on an empty stack? _(Tests defensive design: raise an exception or return a sentinel.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_min_tracker)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.