Min/Max Queue with Two Deques

Problem

Maintain a queue that reports its minimum and maximum in O(1) amortized time.

operations contains "push", "pop", "get_min", or "get_max"; values provides the pushed value. Two monotonic deques track the current minimum and maximum, and pop removes the front element.

Return the list of recorded results (None for push, the removed value or None for pop, and the current extreme or None for the queries).

Hint

Each monotonic deque keeps only the candidates that can still become the extreme.

Test cases

case 1

in: [["push","push","push","get_min","get_max","pop","get_min"],[3,1,2,0,0,0,0]]

expected: [null,null,null,1,3,3,1]

case 2

in: [["pop","get_min","get_max"],[0,0,0]]

expected: [null,null,null]

case 3

in: [["push","get_min","get_max"],[5,0,0]]

expected: [null,5,5]

case 4

in: [["push","push","pop","get_min"],[2,2,0,0]]

expected: [null,null,2,2]

Starter codePython

def min_max_queue(operations, values):
    # Your code here
    pass

4 test cases · run your code against them in the editor