Table of Contents
Min Stack
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 elementvalonto 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,topandgetMinoperations will always be called on non-empty stacks. - At most
3 * 104calls will be made topush,pop,top, andgetMin.
Logic / Trick
Two Stack
Since we want to achieve time complexity of O(1) for all operations, we can use extra space in the solution to achieve faster response time.
- Use the common stack as it is push, pop, top operation
- Additionally, maintain another stack which will keep current minimum on its top of stack for quick return of minimum.
- While pop & push operation, handle both stack correctly.
Single stack with custom struct
- In more optimised version, we can keep track of current minimum in each node we have seen so far.
- This is similar to logic used in Kadane’s algorithm / Prefix sum.
- Keep track of running sum which is max.
- In case of pop, previous node will already have current min which was seen while adding that node.
Approach using 2 stacks
Golang code – 1
type MinStack struct {
stack []int
minStack []int
}
func Constructor() MinStack {
return MinStack{
stack: []int{},
minStack: []int{},
}
}
func (this *MinStack) Push(val int) {
this.stack = append(this.stack, val)
// Update minStack: push the new minimum value
if len(this.minStack) == 0 || val <= this.minStack[len(this.minStack)-1] {
this.minStack = append(this.minStack, val)
}
}
func (this *MinStack) Pop() {
// Remove the top element from stack
if len(this.stack) == 0 {
return
}
top := this.stack[len(this.stack)-1]
this.stack = this.stack[:len(this.stack)-1]
// If the popped value is the current minimum, pop it from minStack
if top == this.minStack[len(this.minStack)-1] {
this.minStack = this.minStack[:len(this.minStack)-1]
}
}
func (this *MinStack) Top() int {
if len(this.stack) == 0 {
return -1 // This case won't occur based on constraints.
}
return this.stack[len(this.stack)-1]
}
func (this *MinStack) GetMin() int {
if len(this.minStack) == 0 {
return -1 // This case won't occur based on constraints.
}
return this.minStack[len(this.minStack)-1]
}
/**
* Your MinStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(val);
* obj.Pop();
* param_3 := obj.Top();
* param_4 := obj.GetMin();
*/
Output
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
************************************
Input
["MinStack","push","push","push","getMin","top","pop","getMin"]
[[],[-2],[0],[-1],[],[],[],[]]
Output
[null,null,null,null,-2,-1,null,-2]
Optimized Approach: Single Stack with Min Information
Golang code – 2
// Optimized Approach: Single Stack with Min Information
type MinStack struct {
stack []element
}
type element struct {
val int
min int
}
func Constructor() MinStack {
return MinStack{
stack: []element{},
}
}
func (this *MinStack) Push(val int) {
// Determine the current minimum
currentMin := val
if len(this.stack) > 0 && this.GetMin() < val {
currentMin = this.GetMin()
}
// Push the value and the current minimum
this.stack = append(this.stack, element{val: val, min: currentMin})
}
func (this *MinStack) Pop() {
// Pop the top element
if len(this.stack) > 0 {
this.stack = this.stack[:len(this.stack)-1]
}
}
func (this *MinStack) Top() int {
if len(this.stack) == 0 {
return -1 // Not expected as per constraints
}
return this.stack[len(this.stack)-1].val
}
func (this *MinStack) GetMin() int {
if len(this.stack) == 0 {
return -1 // Not expected as per constraints
}
return this.stack[len(this.stack)-1].min
}
/**
* Your MinStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(val);
* obj.Pop();
* param_3 := obj.Top();
* param_4 := obj.GetMin();
*/
Output
Case 1
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]Please visit https: https://codeandalgo.com for more such contents.
Leave a Reply