Min Stack

The problem

Build a stack of numbers that can also report its smallest value. You get a list of operation names, operations, and a list values with the arguments of each operation, in the same order. Carry the operations out in order and return a list with one result for each. "MinStack" comes first and creates the empty stack. "push" puts its one argument on top, and "pop" removes the top value. These three give null. "top" gives the top value without removing it, and "getMin" gives the smallest value in the stack. Every operation must take constant time. "pop", "top" and "getMin" are never called on an empty stack.

What to write

function solve(operations: string[], values: number[][]): (number | null)[]

Input
operations = ["MinStack","push","push","push","getMin","pop","top","getMin"]
values = [[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Input
operations = ["MinStack","push","push","pop","getMin"]
values = [[],[1],[1],[],[]]

Output
[null,null,null,null,1]

Constraints

The first operation is MinStack; pop, top and getMin are called only when nonempty.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Every operation must take constant time: the same small amount of work however many values are stored. So getMin may not search the stack. One variable for the smallest value is not enough either, because that value can be popped.

2. Hint 2: Ask a smaller question

   Push 5, then 3, then 7, and write down the smallest value after each push. Now pop twice. What is the smallest value after each pop? Did you have to work it out again, or had you already written it down?

3. Hint 3: Name the pattern

   The task lists operations and wants each of them to be fast. That is the sign of a purpose-built data structure: you combine simple parts and store a little extra. Here, keep a second stack that records, for each value pushed, the smallest value in the stack at that moment. Read the lesson on purpose-built data structure.

4. Hint 4: State the invariant

   The two stacks always have the same height. Each entry of the second stack is the smallest of the value beside it and all the values below. Values under the top never change, so an entry stays correct until it is popped.

5. Hint 5: Sketch the pseudocode

   Keep two lists, stack and mins. push x: append x to stack, and append to mins the smaller of x and the last entry of mins, or x when mins is empty. pop: remove the last entry of both. top is the last entry of stack, getMin the last entry of mins. Answer null for MinStack, push and pop.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Store the minimum at every stack depth in a parallel stack; popping restores the previous minimum.

The slow way

Keep one ordinary stack and, for getMin, look through all its values for the smallest. Push, pop and top stay fast, but getMin takes longer the more values the stack holds, and the task wants constant time for every operation.

The insight

A stack only changes at the top. While a value is in the stack, everything below it stays exactly as it was, so the smallest value from the bottom up to it stays the same too. You can work that minimum out once, at the push, and store it beside the value.

Step by step

1. Keep two stacks: the values, and the smallest value at each depth. The second stack has one entry for each value: the smallest of that value and everything below it. The two grow and shrink together, so the second stack's top is always the minimum of the whole stack.
2. Carry out the operations in order and collect one result for each. All the operations arrive as one list, so the answer is a list too: null for an operation that only changes the stack, a number for one that reads it.
3. A push also records the smallest value in the stack so far. The new minimum is the smaller of the new value and the minimum recorded below it. The first value has nothing below it, so it is its own minimum.
4. A pop removes the value together with its recorded minimum. Removing both keeps the two stacks the same height. The entry now on top of the minimums was worked out for exactly the values that remain.
5. The top and the minimum are the last entries of the two stacks. Reading the end of a list takes one step and changes nothing. No search is needed, because the minimum was worked out when the top value was pushed.

The same numbered steps are the comments in each solution.

function solve(operations, values) {
  // 1. Keep two stacks: the values, and the smallest value at each depth
  const stack = [];
  const mins = [];
  // 2. Carry out the operations in order and collect one result for each
  return operations.map((op, i) => {
    if (op === "MinStack") return null;
    // 3. A push also records the smallest value in the stack so far
    if (op === "push") {
      const n = values[i][0];
      stack.push(n);
      mins.push(Math.min(n, mins.at(-1) ?? Infinity));
      return null;
    }
    // 4. A pop removes the value together with its recorded minimum
    if (op === "pop") {
      stack.pop();
      mins.pop();
      return null;
    }
    // 5. The top and the minimum are the last entries of the two stacks
    return op === "top" ? stack.at(-1) : mins.at(-1);
  });
}

function solve(operations: string[], values: number[][]): (number | null)[] {
  // 1. Keep two stacks: the values, and the smallest value at each depth
  const stack: number[] = [];
  const mins: number[] = [];
  // 2. Carry out the operations in order and collect one result for each
  return operations.map((op, i) => {
    if (op === "MinStack") return null;
    // 3. A push also records the smallest value in the stack so far
    if (op === "push") {
      const n = values[i][0];
      stack.push(n);
      mins.push(Math.min(n, mins.at(-1) ?? Infinity));
      return null;
    }
    // 4. A pop removes the value together with its recorded minimum
    if (op === "pop") {
      stack.pop();
      mins.pop();
      return null;
    }
    // 5. The top and the minimum are the last entries of the two stacks
    return op === "top" ? stack.at(-1)! : mins.at(-1)!;
  });
}

def solve(operations, values):
    # 1. Keep two stacks: the values, and the smallest value at each depth
    stack = []
    mins = []
    # 2. Carry out the operations in order and collect one result for each
    out = []
    for op, args in zip(operations, values):
        result = None
        # 3. A push also records the smallest value in the stack so far
        if op == "push":
            stack.append(args[0])
            mins.append(min(args[0], mins[-1]) if mins else args[0])
        # 4. A pop removes the value together with its recorded minimum
        elif op == "pop":
            stack.pop()
            mins.pop()
        # 5. The top and the minimum are the last entries of the two stacks
        elif op == "top":
            result = stack[-1]
        elif op == "getMin":
            result = mins[-1]
        out.append(result)
    return out

Example 1, traced

Input
operations = ["MinStack","push","push","push","getMin","pop","top","getMin"]
values = [[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Why it works

Each entry of the minimums stack is the smallest of the value beside it and the values below, and those cannot change while the entry exists. A pop removes the top value and its entry together, so the entry left on top always describes exactly the values that remain.

Time and space

Time O(1) per operation, extra space O(n). Every operation adds to the end of a list, removes from it or reads it, and each of those takes constant time: O(1) per operation. The second stack stores one extra number for every value, so n values take O(n) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Do not keep the minimum in a single variable. Once the smallest value is popped, you would have to search for the next smallest. In example 1 the last getMin must answer -2, not -3.
• Record a minimum on every push, even when the new value is not smaller. If you skip it but still pop both stacks, they stop lining up: example 2 pushes 1 twice, pops once and finds the minimums stack empty.
• The first push has no earlier minimum to compare with. Handle the empty case: without it, JavaScript compares with undefined and stores NaN, and Python raises an error.

Pattern

Purpose-built data structure. Builds on Valid Parentheses.

Keep going