LeetCode 155: Min Stack Solution

Master LeetCode problem 155 (Min Stack), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

155. Min Stack

Medium

Stack Design

Problem Explanation

Explanation

To achieve constant time complexity for each function, we can use an additional stack to keep track of the minimum element at each level of the main stack. Whenever we push an element onto the main stack, we also check if it is smaller than the current minimum element. If it is, we push it onto the minimum stack as well. When popping elements, we also check if the element being popped is the current minimum, in which case we pop from the minimum stack as well.

This approach allows us to retrieve the minimum element in constant time by simply peeking at the top of the minimum stack.

Time complexity for each function: O(1)
Space complexity: O(n)

Solution Code

import java.util.Stack;

class MinStack {
    Stack<Integer> stack;
    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();
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 155 (Min Stack)?

This page provides optimized solutions for LeetCode problem 155 (Min Stack) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 155 (Min Stack)?

The time complexity for LeetCode 155 (Min Stack) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 155 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 155 in Java, C++, or Python.

Back to LeetCode Solutions