1928. A Queue That Names Its New Smallest on Every Removal

Challenge1000 ms256 MBSolved by 0%

Build a first-in first-out queue with three operations, one per line:

push v add v to the back, printing nothing pop remove the front value, printing it AND the new smallest value getmin print the smallest value currently held

7 push 4 -> push 2 -> push 7 -> getmin -> 2 pop -> 4 2 4 left; the smallest of what remains (2 and 7) is 2 pop -> 2 7 2 left; only 7 remains pop -> 7 empty

## The rules, stated so the answer is decidable

push prints nothing. getmin prints one value. pop prints two tokens
separated by one space.
pop reports the minimum AFTER the removal, not before. If the removal
empties the queue, the second token is the word empty.
pop on an already empty queue prints the single word empty and nothing
else, so that line has one token where a successful pop has two.
getmin on an empty queue prints empty.
Duplicates are kept and are independent: a queue holding two copies of the
smallest value still reports that value after one of them leaves.

Problem 192 reports the maximum of a queue when asked. That version can be answered lazily, because nothing forces the answer at the moment the set changes. Demanding the new minimum on the SAME line as the removal is the version that forces the structure to be maintained rather than recomputed, and it is the version this problem is about.

## What most people try first

Keep the values in an array and take the minimum of what remains after each removal. Correct, O(n) per pop. With q at 2 * 10^5 half pushes and half pops, that is about 5 * 10^9 comparisons. Removing from the front of an array by shifting everything down is a second O(n) on top of it.

The next instinct is the parallel running-minimum stack from problem 164. It does not transfer to a queue, because a stack only ever changes at the end the running minima were computed from, while a queue removes from the OTHER end, where every recorded minimum was computed with the departing value included.

## Two stacks, each carrying its own running minimum

Build the queue from an in stack and an out stack, and give every entry of both the minimum from the bottom of its own stack up to itself:

push v push (v, min(v, in.top.min)) ontoinpop/getmin ifout is empty, move every entry of in to out, one at a time, recomputing each entry's running minimum as it lands minimum the smaller of in.top.min and out.top.min, over the non-empty ones

Each stack only ever changes at its own top, which is exactly the condition the running-minimum trick needs, and the queue's front is the top of out.

## Why it is correct

The queue's contents are the out stack read top to bottom, followed by the in stack read bottom to top. That partition is a partition of the whole set, so the minimum of the queue is the smaller of the two stacks' minima, and the minimum of a stack whose entries each carry their running minimum is the value at its top. Removing the front pops out, which exposes the entry below it, whose recorded minimum was computed without the departed value, so the number printed after a removal is correct by construction rather than by recomputing.

The transfer preserves order: popping in from its top yields the most recently pushed first, and pushing those onto out leaves the oldest on top, which is the front.

## Why it is fast

Every value is pushed onto in once, transferred to out at most once, and popped once. So the transfer loop runs at most q times across the whole run, and no operation does anything else that is not constant. Each operation is therefore amortised O(1), even though one individual pop can transfer many entries.

## Overflow

Values reach 10^9, which fits in a signed 32 bit integer since the limit is 2147483647. Nothing is summed or multiplied here, so no accumulator can leave 32 bit range, and the running minimum of a set of values is itself one of those values.

## Cost

O(q) in total, amortised constant per operation, with memory proportional to the number of values resident.

Constraints - `1 ≤ q ≤ 200000` - `0 ≤ v ≤ 1000000000` - the queue starts empty - each of `push`, `pop` and `getmin` must run in amortised `O(1)`, so the whole run is `O(q)` - the judge cannot enforce that: the declared tests are small and there is no test generator yet, so taking the minimum of the remaining array on every pop passes them while doing about `5 * 10^9` comparisons at `q = 200000`

Input

The first line contains an integer q, the number of operations. Each of the next q lines is one of push v, pop or getmin.

Output

Print one line for every pop and every getmin. A successful pop prints the removed value and the smallest value remaining, separated by one space, with the word empty in place of that second value if the queue is now empty. A pop on an already empty queue prints the single word empty. A getmin prints the smallest value held, or empty.

Input7 push 4 push 2 push 7 getmin pop pop pop

Output2 4 2 2 7 7 empty

Noteis the worked example, where the minimum changes on one removal and the last removal leaves the queue empty

Input6 push 1 push 5 pop getmin pop pop

Output1 5 5 5 empty empty

Noteremoves the smallest value first, so the reported minimum must jump up rather than stay at the departed value

Input4 pop getmin pop getmin

Outputempty empty empty empty

Notequeries an empty queue, where a pop prints one token and not two

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.

1928. A Queue That Names Its New Smallest on Every Removal

Input

Output

Hints

Similar problems