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
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.