Implement Min Stack
Amazon
BloomBerg
InformaticaThe problem
Design a stack that supports the following operations in constant time: push, pop, top, and retrieving the minimum element.
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.
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(); // returns -3 minStack.pop(); minStack.top(); // returns 0 minStack.getMin(); // returns -2
Input: ["MinStack", "push", "push", "getMin", "push", "pop", "getMin", "top"] [ [ ], [5], [1], [ ], [3], [ ], [ ], [ ] ]
Output: [null, null, null, 1, null, null, 1, 1]
Explanation: MinStack minStack = new MinStack(); minStack.push(5); minStack.push(1); minStack.getMin(); // returns 1 minStack.push(3); minStack.pop(); minStack.getMin(); // returns 1 minStack.top(); // returns 1
Input: ["MinStack", "push", "push", "push", "top", "getMin", "pop", "getMin"] [[], [10], [15], [5], [], [], [], []]
- -105 <= val <=105
- Methods pop, top and getMin operations will always be called on non-empty stacks.
- At most 5*104 calls will be made to push, pop, top, and getMin.
cpp
class MinStack {
public:
MinStack() {
}
void push(int value) {
}
void pop() {
}
int top() {
}
int getMin() {
}
};java
class MinStack {
public MinStack() {
}
public void push(int val) {
}
public void pop() {
}
public int top() {
}
public int getMin() {
}
}python
class MinStack:
def __init__(self):
def push(self, val: int) -> None:
def pop(self) -> None:
def top(self) -> int:
def getMin(self) -> int:javascript
class MinStack {
constructor() {
}
push(val) {
}
pop() {
}
top() {
}
getMin() {
}
}csharp
class MinStack {
public MinStack() {
}
public void Push(int value) {
}
public void Pop() {
}
public int Top() {
}
public int GetMin() {
}
}go
type MinStack struct {
}
func NewMinStack() *MinStack {
}
func (ms *MinStack) Push(val int64) {
}
func (ms *MinStack) Pop() {
}
func (ms *MinStack) Top() int64 {
}
func (ms *MinStack) GetMin() int64 {
}Stuck? Show a way to structure it+
- 01Store the minimum associated with every stack depth.
- 02On push, pair the value with min(value, previous minimum).
- 03Let pop remove both pieces of state so the previous minimum is restored automatically.
- 04Handle duplicate minima and define behavior for an empty stack.
Reference answer
Then expect these follow-ups
Can you encode the previous minimum without an auxiliary stack?
Tests: space optimization
What should operations do on an empty stack?
Tests: API design
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question