1929. A Deque That Knows Its Smallest Value

Build a double-ended queue with five operations, one per line:

pushfront v add v at the front, printing nothing pushback v add v at the back, printing nothing popfront remove the front value and print it popback remove the back value and print it getmin print the smallest value currently held

8 pushback 5 -> pushfront 3 -> the deque, front to back, is 3 5 pushback 1 -> 3 5 1 getmin -> 1 popback -> 1 getmin -> 3 1 has gone, so the smallest of 3 and 5 is 3 popfront -> 3 getmin -> 5

## The rules, stated so the answer is decidable

• Both pushes print nothing. The three other operations each print one line.
• popfront, popback and getmin on an empty deque print empty and change
• nothing.
• A deque of one element has the same element at both ends, so popfront and
• popback both remove it.
• Duplicates are kept and are independent.

Problem 1928 gets the minimum of a QUEUE by splitting it into two stacks, each of which then changes at one end only. A deque changes at both ends by design, so there is no end to hide, and the two halves cannot simply be drained into one another and left there.

## What most people try first

Keep the values in an array and scan for the minimum on every getmin. Correct, O(n) per query, and with q at 2 * 10^5 mostly queries that is about 4 * 10^10 comparisons. Inserting at the front of an array by shifting everything up is a second O(n).

The next instinct is the parallel running-minimum array from problem 164, pushed and popped alongside the values. It gives wrong answers as soon as the two ends are mixed, because the running minimum recorded when a value arrived at the FRONT describes a different set from the one recorded when a value arrived at the BACK, and popping from the far end discards the wrong record.

## Two stacks that are rebalanced, not drained

Hold the deque as two stacks of (value, running minimum) pairs:

front its TOP is the deque's front, so it reads the deque backwards back its TOP is the deque's back

The deque is front read top to bottom, followed by back read bottom to top. Then:

pushfront v push onto front pushback v push onto back popfront if front is empty, REBALANCE, then pop front popback if back is empty, REBALANCE, then pop back getmin the smaller of front.top.min and back.top.min

A rebalance reads out the whole deque in order and splits it into two halves of nearly equal size, rebuilding both stacks and recomputing every running minimum as it goes. Splitting down the middle rather than handing everything to one side is the entire difference from problem 1928, and the reason is below.

## Why it is correct

The two stacks partition the live values, so the minimum of the deque is the smaller of the two stack minima, and each stack's minimum is the number recorded at its own top because each stack only ever changes at its own top. The running minima must be recomputed during a rebalance rather than carried over, because an entry's prefix in the rebuilt stack is a different set of values from its prefix in the old one.

## Why the rebalance is affordable

A rebalance costs O(n) and happens only when one side is empty. After it, both sides hold about n / 2 entries, so the next rebalance on that side needs at least n / 2 pops from it first. Charge each rebalance to the pops that emptied the side and each pop pays a constant amount, which makes every operation amortised O(1). Draining everything to one side instead, as problem 1928 does, would let a single alternating popfront, popback stream force a full transfer on every operation and the whole run would be O(q^2).

## Overflow

Values reach 10^9, which fits in a signed 32 bit integer since the limit is 2147483647. Nothing here is summed or multiplied, and a running minimum is one of the values, so 32 bit arithmetic is safe throughout.

## 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 deque starts empty - each of the five operations 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 scanning for the minimum passes them while doing about `4 * 10^10` comparisons at `q = 200000`