class MinStack {
public:
    MinStack() {}

    void push(int val) {
        const int minVal = (m_minStack != nullptr) ? std::min(m_minStack->val, val) : val;
        Node* top    = new Node{m_stack,    val};
        Node* minTop = new Node{m_minStack, minVal};
        m_stack      = top;
        m_minStack   = minTop;
    }

    void pop() {
        assertNonEmpty();
        Node* top    = m_stack;
        Node* minTop = m_minStack;
        m_stack      = m_stack->next;
        m_minStack   = m_minStack->next;
        delete top;
        delete minTop;
    }

    int top() {
        assertNonEmpty();
        return m_stack->val;
    }

    int getMin() {
        assertNonEmpty();
        return m_minStack->val;
    }

private:
    struct Node {
        Node* next;
        int   val;
    };

    void assertNonEmpty() const {
        if (m_stack == nullptr) {
            throw "empty stack";
        }
    }

    Node* m_stack    = nullptr; // The actual stack.
    Node* m_minStack = nullptr; // Stack of mins.
};

/**
 * 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();
 */