Dare2Solve
To achieve O(1) time complexity for both push, pop, top, and getMin operations, we can use an auxiliary stack to keep track of the minimum elements. By maintaining this auxiliary stack alongside the main stack, we can efficiently retrieve the minimum element whenever required without the need for scanning the entire stack.
Initialize Data Structures:
data
and min_stack
) where:
data
stores all pushed elements.min_stack
keeps track of the minimum elements encountered so far.Push Operation (push(val)
):
val
to the data
stack.min_stack
is empty or val
is less than or equal to the top of min_stack
, push val
onto min_stack
.Pop Operation (pop()
):
data
.min_stack
, also pop from min_stack
.Top Operation (top()
):
data
without removing it.Get Minimum Operation (getMin()
):
min_stack
, which represents the current minimum element in the stack.push(val)
, pop()
, top()
, and getMin()
operations all run in O(1) time complexity because each operation directly accesses or manipulates the top elements of the stacks (data
and min_stack
).min_stack
can store additional elements equal to the number of elements in the main stack (data
), resulting in linear space complexity relative to the number of operations performed.class MinStack {
private:
stack<int> data_stack;
stack<int> min_stack;
public:
MinStack() {
}
void push(int val) {
data_stack.push(val);
if (min_stack.empty() || val <= min_stack.top()) {
min_stack.push(val);
}
}
void pop() {
if (!data_stack.empty()) {
if (data_stack.top() == min_stack.top()) {
min_stack.pop();
}
data_stack.pop();
}
}
int top() {
return data_stack.top();
}
int getMin() {
return min_stack.top();
}
};
class MinStack:
def __init__(self):
self.data = []
self.min_stack = []
def push(self, val: int) -> None:
self.data.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self) -> None:
if self.data:
popped = self.data.pop()
if self.min_stack and popped == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
if self.data:
return self.data[-1]
return -1
def getMin(self) -> int:
if self.min_stack:
return self.min_stack[-1]
return -1
class MinStack {
private Stack<Integer> dataStack;
private Stack<Integer> minStack;
public MinStack() {
dataStack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
dataStack.push(val);
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
public void pop() {
if (!dataStack.isEmpty()) {
int removed = dataStack.pop();
if (removed == minStack.peek()) {
minStack.pop();
}
}
}
public int top() {
return dataStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
var MinStack = function () {
this.stack = [];
}
MinStack.prototype.push = function (val) {
this.stack.push(val)
}
MinStack.prototype.pop = function (val) {
this.stack.pop();
}
MinStack.prototype.top = function (val) {
return this.stack[this.stack.length - 1];
}
MinStack.prototype.getMin = function (val) {
if (!this.stack.length) {
return 0;
}
let min = this.stack[0];
for (var i = 1; i < this.stack.length; i++) {
min = Math.min(min, this.stack[i])
}
return min;
}