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.
Examples:
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
Approach:
-
Initialize stack, Use an array s to store pairs
[value, currentMin]. -
push(val)
- If stack is empty, push
[val, val]. - Else, push
[val, min(val, top’s min)].
- If stack is empty, push
- pop(): Remove the top element using
pop(). - top(): Return the top value:
s[s.length - 1][0]. - getMin(): Return the current minimum:
s[s.length - 1][1].
Visualisation:
Time Complexity:
All operations: O(1)
Space Complexity:
Space Complexity = O(n)
Dry Run:
Input:
Operations: push(3) push(5) push(2) push(1) getMin() pop() getMin() top()
State Transitions:
After push(3): s = [[3, 3]] After push(5): min(5, 3) = 3 → push [5, 3] s = [[3, 3], [5, 3]] After push(2): min(2, 3) = 2 → push [2, 2] s = [[3, 3], [5, 3], [2, 2]] After push(1): min(1, 2) = 1 → push [1, 1] s = [[3, 3], [5, 3], [2, 2], [1, 1]] getMin(): Top element = [1, 1] → min = 1 pop(): Remove top element → [1, 1] s = [[3, 3], [5, 3], [2, 2]] getMin(): Top element = [2, 2] → min = 2 top(): Top element = [2, 2] → value = 2
Final State: s = [[3, 3], [5, 3], [2, 2]] (top to bottom: last element is top)
var MinStack = function() {
this.s = [];
};
MinStack.prototype.push = function(val) {
if(this.s.length === 0){
this.s.push([val, val]);
} else {
let minVal = Math.min(val, this.s[this.s.length - 1][1]);
this.s.push([val, minVal]);
}
};
MinStack.prototype.pop = function() {
this.s.pop();
};
MinStack.prototype.top = function() {
return this.s[this.s.length-1][0];
};
MinStack.prototype.getMin = function() {
return this.s[this.s.length-1][1];
};
class MinStack:
def __init__(self):
self.s = []
def push(self, val: int) -> None:
if not self.s:
self.s.append((val, val))
else:
minVal = min(val, self.s[-1][1])
self.s.append((val, minVal))
def pop(self) -> None:
self.s.pop()
def top(self) -> int:
return self.s[-1][0]
def getMin(self) -> int:
return self.s[-1][1]
import java.util.*;
class MinStack {
List s;
public MinStack() {
s = new ArrayList<>();
}
public void push(int val) {
if (s.isEmpty()) {
s.add(new int[]{val, val});
} else {
int minVal = Math.min(val, s.get(s.size() - 1)[1]);
s.add(new int[]{val, minVal});
}
}
public void pop() {
s.remove(s.size() - 1);
}
public int top() {
return s.get(s.size() - 1)[0];
}
public int getMin() {
return s.get(s.size() - 1)[1];
}
}
class MinStack {
public:
vector> s;
void push(int val) {
if (s.empty()) {
s.push_back({val, val});
} else {
int minVal = min(val, s.back().second);
s.push_back({val, minVal});
}
}
void pop() {
s.pop_back();
}
int top() {
return s.back().first;
}
int getMin() {
return s.back().second;
}
};
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct {
int val;
int min;
} StackNode;
typedef struct {
StackNode* arr;
int top;
int capacity;
} MinStack;
MinStack* minStackCreate() {
MinStack* stack = (MinStack*)malloc(sizeof(MinStack));
stack->capacity = 1000;
stack->top = -1;
stack->arr = (StackNode*)malloc(sizeof(StackNode) * stack->capacity);
return stack;
}
void minStackPush(MinStack* stack, int val) {
int minVal = val;
if (stack->top >= 0 && stack->arr[stack->top].min < val) {
minVal = stack->arr[stack->top].min;
}
stack->arr[++stack->top] = (StackNode){val, minVal};
}
void minStackPop(MinStack* stack) {
if (stack->top >= 0) {
stack->top--;
}
}
int minStackTop(MinStack* stack) {
return stack->arr[stack->top].val;
}
int minStackGetMin(MinStack* stack) {
return stack->arr[stack->top].min;
}
using System;
using System.Collections.Generic;
public class MinStack {
private List<(int val, int min)> s;
public MinStack() {
s = new List<(int, int)>();
}
public void Push(int val) {
if (s.Count == 0) {
s.Add((val, val));
} else {
int minVal = Math.Min(val, s[s.Count - 1].min);
s.Add((val, minVal));
}
}
public void Pop() {
s.RemoveAt(s.Count - 1);
}
public int Top() {
return s[s.Count - 1].val;
}
public int GetMin() {
return s[s.Count - 1].min;
}
}
