Minimum Stack
Minimum Stack
Design a special stack data structure that supports the following operations, all in O(1) time: - PUSH x — push integer x onto the stack - POP — remove the top element from the stack - MIN — return (and print) the current minimum element in the stack
Input format — only if your code reads from stdin
Input format: - First line: integer q (number of operations) - Next q lines: each line is one of: "PUSH x", "POP", or "MIN" Output: for every MIN operation, print the current minimum on its own line. Note: POP and MIN will never be called on an empty stack.
Approach
Maintain two stacks in parallel: the main stack and a min-stack. On PUSH: push to main stack; push to min-stack if new value ≤ current min-stack top (or min-stack is empty). On POP: pop from main; also pop from min-stack if that value equals the main stack's popped value.
Input
Output
- •
1 ≤ q ≤ 10^4, -10^9 ≤ x ≤ 10^9
More Stacks problems
Browse all coding problems →Press Run to test your custom input, or Submit to judge against all test cases.
Sign in to continue
Create a free account to run code, submit solutions and track progress.
- Free forever — no credit card
- 10+ languages with live execution
- Points, streaks & leaderboards