155. Min Stack
Min Stack (LeetCode 155) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Stack Patterns pattern, in the Stack - Min Stack Design subpattern.
How to solve Min Stack
Min Stack is a Min Stack Design problem, part of Stack Patterns. Design a stack that supports push, pop, top, and retrieving minimum element in constant time.
Work towards the solution in these steps:
- Consider each node in the stack having a minimum value. (Credits to @aakarshmadhavan)
The reference solution runs in O(1) time and O(n) space.
The Min Stack solution and editorial walks through the full approach with reference code.
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.
Example 1:
Input ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]
Output [null,null,null,null,-3,null,0,-2]
Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2
Constraints:
- -231 <= val <= 231 - 1
- Methods pop, top and getMin operations will always be called on non-empty stacks.
- At most 3 104 calls will be made to push, pop, top, and getMin.
Topics and companies
Topics: Stack, Design.
Reported in interviews at Capital One, Amazon, Bloomberg, Microsoft, Oracle, eBay, Apple, Coupang.
How to practise Min Stack on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(1) time and O(n) space.
Open Min Stack in the code editor, or read the Min Stack editorial for a worked solution with its approach and complexity analysis.
Where Min Stack sits in the DSA pattern sheet
Problems related to Min Stack
Other problems that use the same Stack - Min Stack Design and Stack Patterns techniques:
- Maximum Frequency Stack — Hard, same subpattern
- Asteroid Collision — Medium, same pattern
- Baseball Game — Easy, same pattern
- Basic Calculator — Hard, same pattern
- Basic Calculator II — Medium, same pattern
- Basic Calculator III — Hard, same pattern
Min Stack FAQ
What is the LeetCode number of Min Stack?
Min Stack is LeetCode problem 155, rated Medium.
What pattern is used to solve Min Stack?
Min Stack is a Min Stack Design problem. It belongs to the Stack Patterns pattern, in the Stack - Min Stack Design subpattern.
What is the time complexity of Min Stack?
The reference solution runs in O(1) time and O(n) space.
Which companies ask Min Stack?
Min Stack has been reported in interviews at Capital One, Amazon, Bloomberg, Microsoft, Oracle, eBay, Apple, Coupang.