164. Stack With a Minimum
Challenge1000 ms256 MBSolved by 0%
Build a stack that also reports its smallest value, with every operation taking constant time.
Read q operations, one per line:
1 x— pushx2— pop, printing nothing3— print the smallest value currently on the stack
If a 2 or 3 happens when the stack is empty, print Empty for a 3 and ignore a 2.
Scanning the whole stack on every 3 is too slow.
Constraints - `1 ≤ q ≤ 200000` - `-1000000000 ≤ x ≤ 1000000000`
Input
The first line contains an integer q.
Each of the next q lines is one operation:
- 1 x — push x
- 2 — pop, printing nothing
- 3 — print the smallest value currently on the stack
Output
Print one line for each 3 operation — the smallest value, or Empty. Operations 1 and 2 print nothing, and a 2 on an empty stack is ignored.
Input6
1 5
1 3
3
2
3
2
Output3
5
Noteshows the minimum returning to an older value after a pop
Input2
3
2
OutputEmpty
Noteasks for the minimum of an empty stack
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution