Min Queue with O(1) Minimum

Problem

Simulate a queue that supports push, pop, and get_min, all in O(1) amortized time.

operations contains "push", "pop", or "get_min"; values provides the pushed value (ignored otherwise). Use two stacks: one for incoming and one for outgoing elements, each carrying a stack of running minima. push records None, pop returns the removed front value or None, and get_min returns the smallest value currently in the queue or None.

Return the list of recorded results.

Hint

Each stack keeps a parallel stack of minima; the queue minimum is the smaller of the two tops.

Test cases

case 1

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

expected: [null,null,1,2]

case 2

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

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

case 3

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

expected: [null,null]

case 4

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

expected: [null,null,5,5,null]

case 5

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

expected: [null,null,1,2,null,1]

Starter codePython

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

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