How to Implement a MinStack with O(1) Push, Pop, and GetMin Operations

A MinStack achieves O(1) time complexity for all operations by augmenting each stack node to store both its value and the minimum of all elements beneath it, eliminating the need to scan the entire structure when retrieving the current minimum.

The MinStack is a fundamental data structure in technical interviews that extends a standard stack to provide constant-time access to the smallest element. In the kdn251/interviews repository, this classic problem is solved using an elegant linked-list approach where each node tracks the running minimum. This article breaks down the implementation found in leetcode/stack/MinStack.java to show exactly how to build a MinStack that guarantees O(1) performance for push, pop, and minimum retrieval.

Core Design Strategy

The implementation relies on a singly-linked list where every node maintains three fields: the element value, a reference to the next node, and crucially, the minimum value present in the stack up to that node. This design ensures that the head of the stack always knows the global minimum without traversing any other nodes.

Node Structure

Each node in the MinStack contains:

• data: The integer value pushed onto the stack
• min: The smallest value in the stack at the time this node becomes the head
• next: Reference to the previous head node

class Node {
    int data;   // element value
    int min;    // minimum up to this node
    Node next;  // link to previous node
}

Head Pointer Management

The stack maintains a single head pointer to the top node. Because every node stores the cumulative minimum, the current minimum of the entire stack is always accessible as head.min. This eliminates the need for auxiliary data structures or costly recalculations.

Implementation Details from leetcode/stack/MinStack.java

The canonical implementation in the kdn251/interviews repository uses straightforward pointer manipulation to maintain O(1) guarantees.

Push Operation (push(int x))

When pushing a new value, the algorithm creates a node whose min field equals the smaller of the new value and the current head's minimum. If the stack is empty, the new value becomes both the data and the minimum.

public void push(int x) {
    Node newNode = new Node();
    newNode.data = x;
    if (head == null) {
        newNode.min = x;
    } else {
        newNode.min = Math.min(x, head.min);
        newNode.next = head;
    }
    head = newNode;
}

Pop Operation (pop())

Removing the top element simply advances the head pointer to head.next. The new head already contains the correct minimum for the remaining elements, requiring no additional computation.

public void pop() {
    head = head.next;
}

Top and GetMin Operations

Retrieving the top element or current minimum accesses the head node's fields directly:

public int top() {
    return head.data;
}

public int getMin() {
    return head.min;
}

Practical Usage Example

The following demonstration shows how the MinStack maintains correct minimums through a sequence of pushes and pops:

MinStack stack = new MinStack();

stack.push(5);
stack.push(2);
stack.push(8);
stack.push(1);

System.out.println(stack.top());    // 1
System.out.println(stack.getMin()); // 1

stack.pop();                       // removes 1
System.out.println(stack.getMin()); // 2
stack.pop();                       // removes 8
System.out.println(stack.top());    // 2
System.out.println(stack.getMin()); // 2

Complexity Analysis

All operations execute in constant time and space:

• Time Complexity: O(1) for push, pop, top, and getMin. Each method performs a fixed number of pointer assignments or arithmetic operations regardless of stack size.
• Space Complexity: O(n) total space where n is the number of elements, with O(1) auxiliary space per node. The solution uses no additional data structures beyond the stack itself.

Alternative Implementations in the Repository

The same design pattern appears in company-specific preparation folders within kdn251/interviews, demonstrating the universal applicability of this approach:

• company/google/MinStack.java
• company/facebook/MinStack.java

These files replicate the core logic found in leetcode/stack/MinStack.java, confirming this as the standard solution for interview scenarios at major technology companies.

Summary

• A MinStack provides O(1) access to the minimum element by storing the running minimum in every node.
• The implementation in leetcode/stack/MinStack.java uses a linked-list structure where each node tracks data, min, and next.
• The push operation calculates Math.min(x, head.min) to maintain the minimum invariant.
• The pop operation simply moves the head pointer, leveraging previously computed minimums.
• This approach appears consistently across multiple interview preparation files in the kdn251/interviews repository.

Frequently Asked Questions

How does MinStack achieve O(1) getMin without scanning all elements?

Each node stores the minimum of all elements below it at the time of insertion. When getMin() is called, it returns head.min, which was precomputed during the push operation. This trades O(1) space per node for O(1) time on every query.

Can MinStack be implemented with an array instead of a linked list?

Yes, though the kdn251/interviews repository uses a linked list for clarity. An array-based implementation would store pairs of (value, currentMinimum) at each index. Both approaches provide O(1) operations, but the linked list version avoids fixed capacity limits and resize overhead.

What happens when pop() removes the last element in this implementation?

After popping the final node, head becomes null. Subsequent calls to top() or getMin() would throw a NullPointerException if not guarded. The original implementation assumes well-formed usage typical of interview constraints where such edge cases are handled by the caller or problem guarantees.

Is this approach better than using two separate stacks?

The single-stack approach used in kdn251/interviews uses less memory than the two-stack alternative (one for values, one for minimums) when duplicate minimum values exist. By storing the minimum with each node, we avoid pushing redundant minimums onto a separate tracking stack, optimizing space while maintaining O(1) time complexity.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}