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

> Learn to build a MinStack for O(1) push, pop, and getMin operations. Discover how augmented nodes store minimums efficiently for faster retrieval.

- Repository: [Kevin Naughton Jr./interviews](https://github.com/kdn251/interviews)
- Tags: how-to-guide
- Published: 2026-03-04

---

**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`](https://github.com/kdn251/interviews/blob/main/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

```java
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`](https://github.com/kdn251/interviews/blob/main/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.

```java
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.

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

```

### Top and GetMin Operations

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

```java
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:

```java
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`](https://github.com/kdn251/interviews/blob/main/company/google/MinStack.java)
- [`company/facebook/MinStack.java`](https://github.com/kdn251/interviews/blob/main/company/facebook/MinStack.java)

These files replicate the core logic found in [`leetcode/stack/MinStack.java`](https://github.com/kdn251/interviews/blob/main/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`](https://github.com/kdn251/interviews/blob/main/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.