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 - 1pop, top and getMin operations will always be called on non-empty stacks.3 * 104 calls will be made to push, pop, top, and getMin.This approach utilizes two stacks. One stack will hold the main elements, while the other stack will keep track of the minimum elements. When you push a value, it's added to the main stack, and if it's less than or equal to the current minimum, it's also pushed onto the min stack. During a pop operation, if the value being popped is the current minimum, it's also popped from the min stack.
The C solution uses simple arrays to maintain the main stack and the minimum stack. We use indices to track the current position in both stacks. The main operations are very similar to basic stack operations but with an additional stack handling minimums.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1) for each operation.
Space Complexity: O(n), where n is the number of elements in the stack.
This approach reduces space usage by storing a pair (value, minimum so far) in a single stack. Each element maintains the current minimum alongside its actual value, providing quick minimum retrieval by just examining the top of the stack.
In C++, the standard stack is used, but each element is stored as a pair. The pair consists of the value and the minimum value at that time. This ensures that when popping, the integrity of the minimum remains intact because each element 'remembers' what the minimum was.
Java
Python
Time Complexity: O(1) for each operation.
Space Complexity: O(n), each element only holds a pair so space is efficient relative to the number of elements.
| Approach | Complexity |
|---|---|
| Using two stacks | Time Complexity: O(1) for each operation. |
| Using a single stack with tuple pairs | Time Complexity: O(1) for each operation. |
Design Min Stack - Amazon Interview Question - Leetcode 155 - Python • NeetCode • 255,349 views views
Watch 9 more video solutions →Practice Min Stack with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor