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. Question: Can the push operation receive any integer value?
   • Answer: Yes, it can accept any integer value including negative integers.
2. Question: Will the pop operation ever be called on an empty stack?
   • Answer: According to the problem constraints, you can assume it will not be called on an empty stack. It is generally best practice to clarify, but the standard problem statement assumes no invalid operations.
3. Question: Should the stack handle memory management, such as avoiding stack overflow for excessively large sizes?
   • Answer: Standard stack implementations do not need to handle this explicitly in the problem constraints.

Strategy:

1. We will use two stacks. One main stack to keep all the elements, and an auxiliary stack to keep track of the minimum elements.
2. During push operation, we push the element onto the main stack. If the auxiliary (min) stack is empty or the current element is smaller than or equal to the top element of the min stack, we push it onto the min stack as well.
3. During pop operation, if the element being popped is the same as the element on the top of the min stack, pop from the min stack.
4. top operation will simply return the top of the main stack.
5. getMin operation will return the top element of the min stack.

Code:

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        if (stack.peek().equals(minStack.peek())) {
            minStack.pop();
        }
        stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

Time Complexity:

• push(): O(1) - Both the main stack and the min stack allow push operations in constant time.
• pop(): O(1) - Both the main stack and the min stack allow pop operations in constant time.
• top(): O(1) - Retrieve the top element of the main stack in constant time.
• getMin(): O(1) - Retrieve the top element of the min stack in constant time.

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?