Queue with constant-time min and max: Frontier Interview's solution

Question: Queue with constant-time min and max

Companies: Google

Difficulty: Medium

Problem statement

Implement a FIFO queue of integers that can also report its smallest and largest element at any time.

Implement the MinMaxQueue class:

MinMaxQueue() creates an empty queue.
enqueue(val: int) -> None adds val at the back.
dequeue() -> int removes and returns the front element.
get_min() -> int returns the smallest element currently in the queue, without removing it.
get_max() -> int returns the largest element currently in the queue, without removing it.

Calling dequeue, get_min or get_max on an empty queue should raise an error.

Constraints

Every operation must run in O(1) time (amortized O(1) is acceptable for enqueue).
Values may repeat and may be negative.
Up to 10^5 operations in total.

Example

q = MinMaxQueue()
q.enqueue(6); q.enqueue(2); q.enqueue(9); q.enqueue(2)
q.get_min()  -> 2
q.get_max()  -> 9
q.dequeue()  -> 6
q.dequeue()  -> 2
q.get_min()  -> 2    # the second 2 is still queued
q.dequeue()  -> 9
q.get_max()  -> 2

Start by describing the simple approach, then make all queries constant time.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

A plain FIFO queue answers enqueue and dequeue in O(1), but finding the
minimum or maximum means scanning every element, which is O(n) per query.
That brute force is the right first sentence; the interviewer wants to see
you remove the scan.

Key observation. When a new value x joins the back of the queue, any
older value larger than x can never be the minimum again: it leaves the
queue before x does, and while both are present x is smaller. So those
older values are dead for min queries and can be dropped from a helper
structure. The same holds for older values smaller than x and max queries.

Optimal design: one queue plus two monotonic deques.

items: the real queue, in arrival order.
mins: a deque that is non-decreasing from front to back. The front is
the current minimum.
maxs: a deque that is non-increasing from front to back. The front is
the current maximum.

enqueue(x): append to items; pop from the back of mins while the back
is strictly greater than x, then append x; do the mirror on maxs.

dequeue(): pop the front of items as x. If mins[0] == x, pop the
front of mins; same for maxs. Values are compared, not identities, so
equal values must be kept in the helpers (pop only on strictly greater /
strictly smaller). With duplicates 3, 3, both copies stay in mins, and
each dequeue of a 3 removes exactly one.

Invariants.

mins holds, in queue order, exactly the elements that are not followed
by a strictly smaller element; its front is the queue minimum.
maxs holds the elements not followed by a strictly larger element; its
front is the queue maximum.
The front of items is either at the front of a helper or not in it at
all (it was dropped because a later value beat it).

Why it's O(1). Each element is pushed onto each helper once and popped
at most once, so the while loops cost O(1) amortized over all operations.
get_min, get_max, peek, size are worst-case O(1).

Alternative. Build the queue from two stacks (inbox, outbox), where
each stack entry stores (value, running_min, running_max). The min of the
queue is the min of the two stack tops. When outbox is empty, move all of
inbox over, recomputing running min/max. Also amortized O(1); it is the
version to reach for if the interviewer wants to extend to any associative
aggregate (gcd, sum mod p, matrix product) rather than just min/max.

Code

from collections import deque
from typing import Deque


class MinMaxQueue:
    """FIFO queue with O(1) amortized enqueue and O(1) dequeue/min/max."""

    def __init__(self) -> None:
        self._items: Deque[int] = deque()
        self._mins: Deque[int] = deque()  # non-decreasing; front = min
        self._maxs: Deque[int] = deque()  # non-increasing; front = max

    def enqueue(self, val: int) -> None:
        self._items.append(val)
        # Keep equals: each duplicate must be removable by its own dequeue.
        while self._mins and self._mins[-1] > val:
            self._mins.pop()
        self._mins.append(val)
        while self._maxs and self._maxs[-1] < val:
            self._maxs.pop()
        self._maxs.append(val)

    def dequeue(self) -> int:
        if not self._items:
            raise IndexError("dequeue from empty queue")
        val = self._items.popleft()
        if self._mins[0] == val:
            self._mins.popleft()
        if self._maxs[0] == val:
            self._maxs.popleft()
        return val

    def peek(self) -> int:
        if not self._items:
            raise IndexError("peek from empty queue")
        return self._items[0]

    def get_min(self) -> int:
        if not self._mins:
            raise IndexError("min of empty queue")
        return self._mins[0]

    def get_max(self) -> int:
        if not self._maxs:
            raise IndexError("max of empty queue")
        return self._maxs[0]

    def __len__(self) -> int:
        return len(self._items)


if __name__ == "__main__":
    import random

    q = MinMaxQueue()
    for v in [4, 1, 7, 1, 3]:
        q.enqueue(v)
    assert (q.get_min(), q.get_max()) == (1, 7)
    assert q.dequeue() == 4 and (q.get_min(), q.get_max()) == (1, 7)
    assert q.dequeue() == 1 and (q.get_min(), q.get_max()) == (1, 7)
    assert q.dequeue() == 7 and (q.get_min(), q.get_max()) == (1, 3)
    assert q.dequeue() == 1 and (q.get_min(), q.get_max()) == (3, 3)
    assert q.dequeue() == 3 and len(q) == 0

    # Randomized check against a brute-force list.
    ref: list[int] = []
    for _ in range(20000):
        if ref and random.random() < 0.45:
            assert q.dequeue() == ref.pop(0)
        else:
            v = random.randint(-5, 5)
            q.enqueue(v)
            ref.append(v)
        if ref:
            assert q.get_min() == min(ref) and q.get_max() == max(ref)
    print("ok")

Complexity

enqueue: O(1) amortized (each value enters and leaves each helper at
most once); a single call can be O(n) when it clears a helper.
dequeue, peek, get_min, get_max, len: O(1) worst case.
Space: O(n). The helpers hold at most n entries each; on a strictly
increasing stream mins holds everything and maxs holds one entry.

Test cases

Enqueue 4, 1, 7, 1, 3: min 1, max 7.
Then dequeue → 4: min 1, max 7.
Dequeue → 1: min still 1 (the second 1 remains), max 7.
Dequeue → 7: min 1, max 3.
Dequeue → 1: min 3, max 3.
Dequeue → 3: queue empty; get_min() raises IndexError.
Empty queue: dequeue(), peek(), get_min(), get_max() all raise.
Single element 5: min 5, max 5; after dequeue, empty.
All equal 2, 2, 2: min and max 2 after each of the first two
dequeues (duplicates must not be collapsed).
Strictly increasing 1, 2, 3, 4: max is always the last value; min
advances 1 → 2 → 3 → 4 as you dequeue.
Strictly decreasing 4, 3, 2, 1: min is always 1; max advances
4 → 3 → 2 → 1.
Negative values and zero: -3, 0, -3: min -3, max 0; dequeue -3,
min still -3.
Interleaved random operations checked against a brute-force list
(in the code above).

Follow-ups

Sliding window min/max. Given an array and window size k, return
the max of each window. Push each element, dequeue once the queue has
more than k elements, read get_max(). O(n) total. A common next step
is "count subarrays where max − min ≤ K", solved with two pointers and
this queue.
Store indices instead of values. If the interviewer objects to the
value-equality check, give each element a sequence number and keep
(seq, value) in the helpers; dequeue pops the helper front when its
seq matches. This also works for objects with a comparison key.
Worst-case O(1) enqueue. The monotonic approach is only amortized.
Discuss the two-stack version with incremental (lazy) transfer, or note
that real-time queues (Hood–Melville style) de-amortize at higher
constant cost. Usually a discussion point, not code.
Other aggregates. Support get_gcd() or get_sum_mod_p(). Monotonic
pruning only works for selection-type aggregates (min/max); switch to the
two-stack design with running aggregates, which works for any
associative operation.
Bounded capacity / thread safety. A fixed-capacity version that
evicts the oldest element on overflow is just dequeue then enqueue.
For concurrent producers and consumers, one lock around all three
deques is simplest; discuss why helper and queue updates must be atomic
together.

Interviewer expectations

Mid-level (L4)

States the O(n) scan baseline, then reaches the monotonic deque idea,
possibly with hints (often by first recalling the min-stack problem).
Correct code for enqueue, dequeue, get_min, get_max, including
empty-queue handling.
Explains why the amortized cost is O(1).

Senior (L5)

Gets duplicates right without prompting (strict comparison when popping)
and can justify it with an example.
States the helper invariants clearly and tests edge cases unasked.
Knows the two-stack alternative and when each is preferable; solves the
sliding-window follow-up quickly.

Staff (L6+)

Separates amortized from worst-case bounds and discusses latency-sensitive
use (de-amortization).
Generalizes: monotonic pruning for min/max vs. two-stack running
aggregates for any associative operation.
Discusses API design choices (exceptions vs. sentinel, generic key
functions, sequence numbers) and concurrency concerns.