Solution: Tracking the Minimum

The direct approach is to traverse the list on every getMin call and keep the smallest value seen. That gives the right answer, but the traversal costs $O(n)$.

A single saved minimum does not work, because it breaks when we pop the minimum off the stack. To find the new minimum after popping, we would need to scan the remaining nodes, which is again $O(n)$.

We saw this problem in the Chapter 9 practice: the linked MaxList gives every node a maxPointer that points to the node holding the largest value so far. The same idea works here: give every node a minPointer that points to the node holding the smallest value at or below it.

private static class Node {
  Integer value;
  Node minPointer;  // the node holding the smallest value at or below this one
  Node next;

  Node(Integer value) {
    this.value = value;
  }
}

The class itself looks exactly like LinkedStack: a single head field, with pop, top, and isEmpty identical to the chapter’s versions (Integer in place of T), so we will not repeat them. Only push is different: if the new item is strictly smaller than the current minimum, the new node points at itself; otherwise it copies the pointer from the node below it.

@Override
public void push(Integer item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  Node newNode = new Node(item);
  if (isEmpty() || item < head.minPointer.value) {
    newNode.minPointer = newNode;  // the new item is the new minimum
  } else {
    newNode.minPointer = head.minPointer;
  }
  newNode.next = head;
  head = newNode;
}

getMin follows one pointer from the top:

@Override
public Integer getMin() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  return head.minPointer.value;
}

Notice that pop does not need any extra work. The minPointer of the node being removed goes away with it, and the node below it already points to the correct minimum.

Let’s trace a sequence of operations to see how the minPointer works. The m→ annotation under each node shows the value that node’s minPointer points to.

After push(5), the only node is its own minimum, and getMin() returns 5:

         ┌───┐
top ───▶ │ 5 │ ──▶ null
         └───┘
           ▲
          m→5

After push(2), the new item is strictly smaller, so its node points at itself; getMin() returns 2:

         ┌───┐      ┌───┐
top ───▶ │ 2 │ ──▶  │ 5 │ ──▶ null
         └───┘      └───┘
           ▲          ▲
          m→2        m→5

After push(7), the new item is not smaller, so it copies the pointer from the node below it; getMin() still returns 2:

         ┌───┐      ┌───┐      ┌───┐
top ───▶ │ 7 │ ──▶  │ 2 │ ──▶  │ 5 │ ──▶ null
         └───┘      └───┘      └───┘
           ▲          ▲          ▲
          m→2        m→2        m→5

Now a pop() removes the 7, and getMin() returns 2:

         ┌───┐      ┌───┐
top ───▶ │ 2 │ ──▶  │ 5 │ ──▶ null
         └───┘      └───┘
           ▲          ▲
          m→2        m→5

Another pop() removes the 2, and getMin() returns 5:

         ┌───┐
top ───▶ │ 5 │ ──▶ null
         └───┘
           ▲
          m→5

Duplicate values work too. Push a 2, then another 2: the newer 2 is not strictly smaller, so it points to the older 2 below it.

         ┌───┐      ┌───┐
top ───▶ │ 2 │ ──▶  │ 2 │ ──▶ null
         └───┘      └───┘
           ▲          ▲
          m→2        m→2

Both nodes show m→2 because the annotation shows the value, not the node. The two pointers go to different nodes, and only the older 2 points at itself. Pop the newer 2 and the older 2 still points at itself, so getMin() returns 2 before and after the pop.

Can a minPointer ever point to a popped node? No. It always points to a node at or below its own, and a stack removes only from the top, so the node it points to is still in the stack.

So every operation, getMin included, is $O(1)$ worst case. The cost is one extra reference per node: $O(n)$ auxiliary space.