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
Hiring now
Software engineer roles are open right now
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY
Next question