The Min Tracker

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Citadel

Problem

How can a MinStack class keep push, pop and get_min all running in constant time, where get_min reports the smallest value currently on the stack without removing it? run_operations replays a log of operations against their arguments lists, the first entry building a fresh stack, and returns one result per entry.

The stack remembers the best it ever saw.

Example

Input:

arguments = [[],[-2],[0],[-3],[],[],[]], operations = ["MinStack","push","push","push","get_min","pop","get_min"]

Output:

[null,null,null,null,-3,null,-2]

Worked solution and explanation

This is rollback-able state dressed up as a data structure question. Anyone can push and pop; the skill is keeping the minimum right after the minimum leaves. A single current_min has no memory of what came before it, so the moment '-3' is popped it either keeps reporting '-3', a value that is gone, or rescans everything left, which quietly turns a constant-time operation into O(n). The fix is to remember the minimum at every depth, so removing the top hands back an answer that was already correct.

Why the minimum needs a history

Step 1: Store a minimum beside every value

Each position holds two things: the value pushed, and the smallest value from the bottom up to that position. The minimum of the whole stack is then the record at the top, and the record underneath was correct before the top was ever pushed.

Step 2: Compute the slot's minimum on push

Compare the new value with mins[size - 1], or take the value itself when the stack is empty. That one record already summarises everything below, so a single comparison is all a push costs.

Step 3: Pop by moving the top

The instance tracks size, the number of live positions. A pop decrements it and returns the value that was there; the freed position is overwritten by the next push instead of shrinking and regrowing the lists. Nothing is recomputed, so the previous minimum is simply back on top.

Step 4: Replay the log in run_operations

Walk operations and arguments together, build the MinStack on the leading 'MinStack' entry, call the matching method with the unpacked arguments, and record None for everything except get_min.

The solution

Per-slot minimums behind a top index, driven by `run_operations`
class MinStack:
    def __init__(self):
        self.values = []
        self.mins = []
        self.size = 0

    def push(self, val):
        if self.size == 0 or val <= self.mins[self.size - 1]:
            slot_min = val
        else:
            slot_min = self.mins[self.size - 1]

        if self.size == len(self.values):
            self.values.append(val)
            self.mins.append(slot_min)
        else:
            # Reuse a position freed by an earlier pop.
            self.values[self.size] = val
            self.mins[self.size] = slot_min
        self.size += 1

    def pop(self):
        self.size -= 1
        return self.values[self.size]

    def get_min(self):
        return self.mins[self.size - 1]


def run_operations(operations, arguments):
    results = []
    min_stack = None
    for operation, args in zip(operations, arguments):
        if operation == "MinStack":
            min_stack = MinStack()
            results.append(None)
        elif operation == "push":
            min_stack.push(*args)
            results.append(None)
        elif operation == "pop":
            min_stack.pop()
            results.append(None)
        elif operation == "get_min":
            results.append(min_stack.get_min())
    return results
One running minimum
current_min is a single number. Push keeps it current in O(1), but popping the minimum leaves it stale, and recovering means scanning what is left: O(n) per pop or per get_min.
A minimum per position
mins[i] is the minimum of positions 0 through i. Push writes one comparison's result, pop moves size, get_min reads mins[size - 1]: O(1) for all three, paid for with a second list.

Common follow-up questions