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
Solid implementation of the Min Stack data structure. The logic for maintaining the min element in constant time is correctly implemented. The code is well-structured, and the documentation is with very clear examples.
Thank you