NeetCode 150: Min Stack

Table of contents

The Problem

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack. You must implement a solution with O(1) time complexity for each function.

An Example

Image taken from LeetCode.

The Approach

The goal is to create a Stack-like class that supports the retrival of the minimum element in O(1) time complexity. Thus, caching of data is required to meet this requirement.

I will be basing my approach on the creation of a LinkedList with a sentinel node (null safe) to keep track of the element at the top of the stack.

Each Node will cache the smallest value it has seen by referencing the previous Node during insertion.

A visual representation created by me.

My Solution

class MinStack {
    class Node {
        Node next = null;
        int value;
        int minValueSoFar;

        public Node(Node next, int val, int minVal) {
            this.next = next;
            this.value = val;
            this.minValueSoFar = minVal;
        }
    }

    Node sentinel;
    int currentMinimum;
    int size = 0;

    public MinStack() {
        sentinel = new Node(null, 44, 44); // 44 is a placeholder value.
    }
    
    // Adds a new node to the stack, checks if val is smaller than the
    // val of the current top element of the stack.
    public void push(int val) {
        if (size == 0) {
            Node node = new Node(sentinel.next, val, val);
            sentinel.next = node;
        } else {
            int minVal = getSmallerElement(val, sentinel.next.minValueSoFar);
            Node node = new Node(sentinel.next, val, minVal);
            sentinel.next = node;
        }
        size++;
    }
    
    // Removes the element on the top of the stack.
    public void pop() {
        if (size > 0) {
            sentinel.next = sentinel.next.next;
            size--;
        }
    }
    
    // Returns the top element of the stack.
    public int top() {
        if (size > 0) {
            return sentinel.next.value;
        } else {
            return -1;
        }
    }
    
    // Returns the minimum element in the stack by checking the top
    // node's minValueSoFar.
    public int getMin() {
        if (size > 0) {
            return sentinel.next.minValueSoFar;
        } else {
            return -1;
        }
    }

    // Returns the smaller element.
    private int  getSmallerElement(int val1, int val2) {
        if (val1 < val2) {
            return val1;
        } else {
            return val2;
        }
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

The respective explanations is commented at the top of each method.