Finding the minimum element of a stack of numbers

Question

As part of an online programming challenge, I wrote a program that implements a stack of integers, supporting adding and removing elements, finding the last inserted element, and the minimum element. The premise is that all methods must be implemented in constant O(1) time.

In my code, I opted to use LinkedLists for the internal stacks, as with an array-based data structure such as ArrayDeque, ArrayList, and the legacy Stack, there's the risk of running out of internal capacity in the specific case of adding a number, which would thus make it have a potential time complexity of O(n) (worst case). That class also conveniently implements the Deque interface, which doubles as the standard generic interface for stacks.

In my solution, I make use of three stacks: the primary internal stack used for all methods, a stack with the last known minimum number, and one that keeps count of the amount of numbers added since the last known minimum number was added (that is, the number of times to pop before the top/last entry in the known minimum stack is no longer in the primary stack). I keep track of the topmost minimum as a variable so it can be modified on the fly easily, and only when a new minimum is added do I push that value onto the third stack (and reset the variable to 0).

Here's my code:

import java.util.Deque;
import java.util.LinkedList;

class MinStack {
    
    private Deque<Integer> stack;
    private Deque<Integer> min;
    private Deque<Integer> minStepsCount;
    private int minSteps;

    public MinStack() {
        stack = new LinkedList<>();
        min = new LinkedList<>();
        minStepsCount = new LinkedList<>();
        minSteps = 0;
    }
    
    public void push(int val) {
        stack.push(val);
        if (min.isEmpty() || min.peek() > val) {
            min.push(val);
            minStepsCount.push(minSteps);
            minSteps = 0;
        }
        else
            minSteps++;
    }
    
    public void pop() {
        stack.pop();
        if (minSteps == 0) {
            min.pop();
            minSteps = minStepsCount.pop();
        }
        else
            minSteps--;
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return min.peek();
    }
}

The code functions correctly and passes all test cases, including the stringent time limits to ensure O(1) compliance. However, when it comes to memory usage, when considering all others' solutions to the problem, they fall into a bimodal distribution, meaning that solutions to the problem fall into two clear, distinct categories, with one taking up less memory and one taking up more memory. In this case, the less-memory solution uses an average of 40 MB, while the more-memory solution uses an average of 45 MB. My solution falls into the more-memory category.

What can I do to reduce the memory usage of this program so it falls into the less-memory category, and is there anything else that could use improvement in my code?

Answer 1

Bad behaviour

Your getMin() method will throw a NullPointerException on empty stack, when more canonical exception for reporting that condition is NoSuchElementException. Also, your pop() method (on empty stack) already throws a NoSuchElementException, but its message does not specify the reason of the exception thrown. I suggest you do the following:

public E pop() {
    if (primaryStack.isEmpty()) {
        throw new NoSuchElementException("Popping from an empty stack.");
    }
    
    minimumStack.removeLast();
    return primaryStack.removeLast();
}

LinkedList vs. ArrayDeque

Please, change LinkedList to ArrayDeque for the following reasons:

1. It is true, that the internal array of ArrayDeque must be made longer when it becomes full, which is \$\Theta(n)\$. However, ArrayDeque is designed in such manner, that the amortized time complexity of adding on both the ends of the ArrayDeque is \$\Theta(1)\$. (See the proof.)

2. Almost full ArrayDeque is likely to occupy less space than a LinkedList with the same content, since ArrayDeque uses one reference per element (LinkedList uses 3: one for the element, one for the previous node and one for the next node). Also, the internal nodes of the linked list data structures are scattered all over the heap memory, so iterating over linked lists will produce a hell lot of CPU cache misses. (See this SO question.)

Overkilling it

You don't really need minStepsCount and minSteps; see below.

Summa summarum

I suggest the following reimplementation of a minimum stack. Note that making it a generic class is not that hard.

package com.yourcompany.util;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.NoSuchElementException;
import java.util.Objects;

/**
 * This class implements a LIFO stack providing a constant time method for 
 * getting the minimum value in the stack.
 * 
 * @author Rodion "rodde" Efremov
 * @param <E> the element type.
 * @version 1.6 (Jan 24, 2022)
 * @since 1.6 (Jan 24, 2022)
 */
public class MinStack<E extends Comparable<? super E>>   {

    private final Deque<E> primaryStack = new ArrayDeque<>();
    private final Deque<E> minimumStack = new ArrayDeque<>();
    
    public void push(E element) {
        Objects.requireNonNull(element, "The input element is null.");
        primaryStack.addLast(element);
        
        if (minimumStack.isEmpty() ||
                element.compareTo(minimumStack.getLast()) < 0) {
            // Introduce new minimum:
            minimumStack.addLast(element);
        } else {
            // Copy the minimum:
            minimumStack.addLast(minimumStack.getLast());
        }
    }
    
    public E pop() {
        if (primayStack.isEmpty()) {
            throw new NoSuchElementException("Popping from an empty stack.");
        }
        
        minimumStack.removeLast();
        return primaryStack.removeLast();
    }
    
    public E top() {
        checkNotReadingFromEmptyStack();
        return primaryStack.getLast();
    }
    
    public E min() {
        checkNotReadingFromEmptyStack();
        return minimumStack.getLast();
    }
    
    private void checkNotReadingFromEmptyStack() {
        if (primaryStack.isEmpty()) {
            throw new NoSuchElementException("Reading from an empty stack.");
        }
    }
}