Min Stack
Design a stack that supports the following operations in constant time:
-
push(x) – Push element x onto the stack.
-
pop() – Removes the element on the top of the stack.
-
top() – Get the top element.
-
get_min() – Retrieve the minimum element in the stack.
All operations must run in O(1) time.
You may assume that all input values are valid and that operations will be called on non-empty stacks where applicable.
Example
Input: operations = ["MinStack", "push", "push", "push", "getMin", "top", "pop", "getMin"] arguments = [[], [1], [2], [3], [], [], [], []] Output: expected = [None, None, None, None, 1, 3, None, 1]
Explanation -
Stack = [1, 2, 3], minimum is 1 throughout.
top() is 3, pop removes 3, getMin() still returns 1.
To keep track of the minimum element at each point in the stack, we store a pair [value, current_minimum]
So the stack becomes a list of pairs where each element holds:
- The actual value pushed.
- The minimum value of the stack up to that point.
Algorithm
init -> None Initializes an empty list stack that will store pairs [value, current_min].
push(self, value: int) -> None If the stack is empty, both the value and the minimum are value.
Otherwise: cur_min = self.stack[-1][1] gives the current minimum.
We push a new pair: [value, min(value, cur_min)].
This way, each push stores the updated min.
pop(self) -> None Simply pops the top element (a pair) from the stack. Since each element stores its own min, popping one doesn't affect earlier elements' min tracking.
top(self) -> int Returns the actual value of the top element using self.stack[-1][0].
get_min(self) -> int Returns the current minimum in constant time using self.stack[-1][1].
from typing import List
class min_stack:
def __init__(self) -> None:
self.stack = []
def push(self, value: int) -> None:
if not self.stack:
self.stack.append([value, value])
else:
cur_min = self.stack[-1][1]
self.stack.append([value, min(cur_min, value)])
def pop(self) -> None:
return self.stack.pop()
def top(self) -> int:
return self.stack[-1][0]
def get_min(self) -> int:
return self.stack[-1][1]Time Complexity: O(1) per operation.
push(val): Constant time, as it only involves a top-element lookup and comparison.
pop(): O(1) stack operation.
top(): Accesses the top element’s value via index [-1][0]which takes O(1).
get_min(): O(1) with no need to traverse the stack.
Space Complexity: For n push operations, we store a tuple [value, current_min] for each element.
This doubles the storage per element, but still remains linear: O(2n) → O(n)