LeetCode Min Stack: Optimal Memory Implementation

Overview

To reduce the memory cost the LeetCode Min Stack problem, we do not need to store the minimum value associated with those are larger than the current minimum.

LeetCode Min Stack Problem

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

  • push(x) — Push element x onto stack.
  • pop() — Removes the element on top of the stack.
  • top() — Get the top element.
  • getMin() — Retrieve the minimum element in the stack.

Solution and Analysis

This min stack problem is an easy one. It is not hard to come up with the basic solution to associate each pushed element with a current minimum value among the all the elements in the min stack. The space cost would be always O(N). A bit optimized version could make the extra memory cost less than O(N), if we got lucky it could even be O(1) in the best case. Here is the code accepted by LeetCode OJ which passes this Min Stack Problem

class MinStack {
    public:
        void push(int x) {
            eleStack.push(x);
            if (minStack.empty() || x <= minStack.top())
                minStack.push(x);
        }

        void pop() {
            if (eleStack.empty()) return;
            if (eleStack.top() == minStack.top())
                minStack.pop();
            eleStack.pop();
        }

        int top() { return eleStack.top(); }

        int getMin() {
            return minStack.top();
        }

    private:
        stack<int> eleStack;
        stack<int> minStack;
};

Summary

To reduce the memory cost the LeetCode Min Stack problem, we do not need to store the minimum value associated with those are larger than the current minimum. For more information, you could also refer to the LeetCode old post: “Stack that Support Push, Pop, and GetMin in Constant Time“.

Written on November 16, 2014