TheAlgorithms
implementation of min stack
Problem Description: Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Operations:
push(x) — Push element x onto the stack.
pop() — Removes the top element from the stack.
top() — Retrieves the top element.
getMin() — Retrieves the minimum element in the stack.
Example:
min_stack = MinStack() min_stack.push(-2) min_stack.push(0) min_stack.push(-3) print(min_stack.getMin()) # Output: -3 min_stack.pop() print(min_stack.top()) # Output: 0 print(min_stack.getMin()) # Output: -2
Pattern: Stack with extra information / Two-stack approach
Time Complexity:
push: O(1)
pop: O(1)
top: O(1)
getMin: O(1)
Space Complexity:
O(n) extra space for the auxiliary stack to store minimums
