The strongest of the month
A seismological service keeps an event feed: new earthquakes join the end, and those older than a month leave from the front. The duty officer needs to know at any moment the strongest of those currently in the feed. The feed is a queue, and to the usual queue operations is added the question “what is the maximum?”.
One of the tests is the real USGS catalogue: all earthquakes of magnitude 5 and above over 2015–2025 in order; after each one, events older than 30 days leave the feed, and then the duty officer asks for the maximum. Magnitudes are multiplied by 100.
Input
The first line holds the number of operations q (1 ≤ q ≤ 300,000). Then one operation per line:
+ x: put the number x at the end of the queue (0 ≤ x ≤ 10⁹);-: remove the number at the front of the queue (the queue is not empty);?: ask for the largest number in the queue (the queue is not empty).
Output
For each ? question, the largest number in the queue at that moment, one per line.
Examples
Example 1
9 + 5 + 3 ? + 7 ? - ? - ?
5 7 7 7
Example 2
11 + 9 + 1 + 8 + 2 ? - ? - ? - ?
9 8 8 2
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 7 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Going through the whole queue for each question is O(n) per question. The fourth test: a hundred thousand numbers in the queue and a hundred thousand questions. For a stack the maximum is easy to know: let each entry remember the maximum of all the entries beneath it. Why does this work for a stack but not for a queue?
2Hint 2
In a stack everything changes at one end, and an entry’s “maximum beneath” never goes stale. What if the queue is assembled from two stacks?
3The idea
A queue on two stacks. New numbers go on the “input” stack. We take from the front via the “output” stack; when it is empty, we pour the whole input stack into it: pouring reverses the order, and the oldest number ends up on top. Each entry in both stacks stores the pair “number, maximum from the bottom of the stack up to this entry”. Then the maximum of the whole queue is the larger of the maximums at the tops of the two stacks.
4Walkthrough
Three operations. + x: push onto the input stack the pair (x, max(x, the maximum at its top)). -: if the output stack is empty, pour the input one into it, recomputing the maximums for the output stack; then pop the top of the output stack. ?: compare the maximums at the tops of whichever stacks are not empty.
Pouring looks expensive, but each number is poured exactly once in its life: it went on the input stack, once moved to the output one, then left. So all q operations take O(q) actions: each operation costs O(1) amortised, by the same accounting as append on a dynamic array.
There is another solution, a monotonic queue: a deque that holds only the numbers that still have a chance of becoming the maximum, in decreasing order. It is linear too; it is covered in the article on the monotonic stack.
On the real catalogue the answers read like a chronicle. The strongest events in it are the magnitude 8.3 at Illapel, Chile, in September 2015 and the 8.8 off Kamchatka in July 2025: after each of them the answer to “?” stays at 830 and at 880 for 30 days.
4+Solution
5Complexity
O(q) for all operations, O(1) amortised for each. Memory is O(n) for the numbers in the queue.
6Common mistakes
- Going through the queue for each question. Correct, but quadratic on the fourth test.
- One shared maximum. Storing a single number “the current maximum” does not work: when the maximum leaves from the front, it is unknown who is next (the second example).
- Pouring on every “-”. Pour only when the output stack is empty. Otherwise the order gets mixed up, and the time becomes quadratic.
- A heap with lazy deletion works, but at O(log n) per operation, and it requires remembering which numbers have already left.