algoadvance

Leetcode 155. Min Stack

Problem Statement

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.

Clarifying Questions

1. Q: Should the stack handle only integer values?
   • A: Yes, the stack will handle integers.
2. Q: Can we use additional data structures?
   • A: Yes, you can use additional data structures as long as the time complexity requirements are met.
3. Q: Are there any constraints on the values that can be pushed (like negative numbers or very large numbers)?
   • A: No constraints are specifically mentioned, implying any integer is valid.
4. Q: What should happen on a pop operation if the stack is empty?
   • A: This shouldn’t happen as per typical LeetCode problems, but ensuring robust code for this case avoids runtime errors.
5. Q: Should we handle exceptions or errors for operations on an empty stack?
   • A: Typically, LeetCode problems assume valid operations. However, graceful handling of such cases is good practice.

Strategy

To maintain the minimum element, we can use an auxiliary stack that keeps track of the minimums. Here’s the idea:

1. Main Stack: The regular stack to store all the values.
2. Min Stack: An auxiliary stack to store the minimum values at each level.

When pushing a new value:

• Add it to the main stack.
• Compare it with the current minimum (top of the min stack) and push the smaller value onto the min stack.

When popping a value:

• Pop from the main stack.
• Pop from the min stack.

When retrieving the minimum:

• The top of the min stack is always the current minimum.

This ensures all operations take constant time O(1).

Code

#include <stack>
#include <stdexcept>

class MinStack {
public:
    MinStack() {}

    void push(int val) {
        mainStack.push(val);
        if (minStack.empty() || val <= minStack.top()) {
            minStack.push(val);
        } else {
            minStack.push(minStack.top());
        }
    }

    void pop() {
        if (!mainStack.empty()) {
            mainStack.pop();
            minStack.pop();
        }
    }

    int top() {
        if (!mainStack.empty()) {
            return mainStack.top();
        }
        throw std::runtime_error("Stack is empty");
    }

    int getMin() {
        if (!minStack.empty()) {
            return minStack.top();
        }
        throw std::runtime_error("Stack is empty");
    }

private:
    std::stack<int> mainStack;
    std::stack<int> minStack;
};

Time Complexity

• Push Operation: O(1) because pushing onto a stack takes constant time.
• Pop Operation: O(1) because popping from a stack takes constant time.
• Top Operation: O(1) because accessing the top element takes constant time.
• Get Min Operation: O(1) because accessing the top element of the min stack takes constant time.

This implementation ensures all operations have the required O(1) time complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?