Problem

Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

Input:
push_rear(1)
push_rear(3)
push_rear(0)
get_min()
pop_front()
get_min()
Output:
0
1
Explanation:
After pushing 1, 3, and 0, the queue is [1, 3, 0]. The minimum is 0.
After popping the front element (1), the queue is [3, 0]. The minimum is now 0.

Solution

Method 1 - Using Two Stacks

You can implement a stack with O(1) operations for pop(), push(), and get_min() by storing the current minimum with each element. For instance, the stack [4, 2, 5, 1] (1 is the top) would be represented as [(4, 4), (2, 2), (5, 2), (1, 1)]. Refer to the Min Stack Problem for more details.

To construct a queue using two stacks, push elements into one stack and pop them from another. If the second stack is empty during a pop operation, move all elements from the first stack to the second. The minimum element of the queue can be found by comparing the smallest elements from each of the two min-stacks. This method ensures O(1) time complexity for get_min() and push(), and amortized O(1) time complexity for pop().

You can implement a stack with O(1) pop(), push() and get_min(): just store the current minimum together with each element. So, for example, the stack [4, 2, 5, 1] (1 on top) becomes [(4, 4), (2, 2), (5, 2), (1, 1)].

See here for the Min Stack. Then we have Implement Queue using Stacks

Method 2 - Using Three Queues

Method 1 can be time-consuming in an interview setting. Instead, consider using three queues. The first queue handles enqueue and dequeue operations in O(1) time. The other two queues track the minimum element, and we adjust these queues during push and pop operations to maintain the minimum element in O(1) time.

Pseudocode

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Queue q, minq1, minq2;
isMinq1Current = true;
void push(int a) {
	q.push(a);
	if (isMinq1Current) {
		if (minq1.empty) minq1.push(a);
		else {
			while (!minq1.empty && minq1.top<= a) minq2.push(minq1.pop());
			minq2.push(a);
			while (!minq1.empty) minq1.pop();
			isMinq1Current = false;
		}
	} else {
		//mirror if(isMinq1Current) branch. 
	}
}

int pop() {
	int a = q.pop();
	if (isMinq1Current) {
		if (a == minq1.top) minq1.pop();
	} else {
		//mirror if(isMinq1Current) branch.    
	}
	return a;
}

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

class Solution {
    private Queue<Integer> q, minq1, minq2;
    private boolean isMinq1Current;

    public Solution() {
        q = new LinkedList<>();
        minq1 = new LinkedList<>();
        minq2 = new LinkedList<>();
        isMinq1Current = true;
    }

    public void push(int a) {
        q.add(a);
        if (isMinq1Current) {
            if (minq1.isEmpty()) {
                minq1.add(a);
            } else {
                while (!minq1.isEmpty() && minq1.peek() <= a) {
                    minq2.add(minq1.poll());
                }
                minq2.add(a);
                while (!minq1.isEmpty()) {
                    minq1.poll();
                }
                isMinq1Current = false;
            }
        } else {
            // Handle when minq2 is current
            if (minq2.isEmpty()) {
                minq2.add(a);
            } else {
                while (!minq2.isEmpty() && minq2.peek() <= a) {
                    minq1.add(minq2.poll());
                }
                minq1.add(a);
                while (!minq2.isEmpty()) {
                    minq2.poll();
                }
                isMinq1Current = true;
            }
        }
    }

    public int pop() {
        if (q.isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        int a = q.poll();
        if (isMinq1Current) {
            if (a == minq1.peek()) {
                minq1.poll();
            }
        } else {
            if (a == minq2.peek()) {
                minq2.poll();
            }
        }
        return a;
    }

    public int getMin() {
        if (minq1.isEmpty() && minq2.isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        if (isMinq1Current) {
            return minq1.peek();
        } else {
            return minq2.peek();
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

class Solution:
    def __init__(self):
        self.q = deque()
        self.minq1 = deque()
        self.minq2 = deque()
        self.isMinq1Current = True

    def push(self, a: int) -> None:
        self.q.append(a)
        if self.isMinq1Current:
            if not self.minq1:
                self.minq1.append(a)
            else:
                while self.minq1 and self.minq1[0] <= a:
                    self.minq2.append(self.minq1.popleft())
                self.minq2.append(a)
                while self.minq1:
                    self.minq1.popleft()
                self.isMinq1Current = False
        else:
            if not self.minq2:
                self.minq2.append(a)
            else:
                while self.minq2 and self.minq2[0] <= a:
                    self.minq1.append(self.minq2.popleft())
                self.minq1.append(a)
                while self.minq2:
                    self.minq2.popleft()
                self.isMinq1Current = True

    def pop(self) -> int:
        if not self.q:
            raise IndexError("pop from an empty queue")
        a = self.q.popleft()
        if self.isMinq1Current:
            if a == self.minq1[0]:
                self.minq1.popleft()
        else:
            if a == self.minq2[0]:
                self.minq2.popleft()
        return a

    def get_min(self) -> int:
        if not self.minq1 and not self.minq2:
            raise IndexError("min from an empty queue")
        if self.isMinq1Current:
            return self.minq1[0]
        else:
            return self.minq2[0]

Method 3 - Using 2 Deque

To ensure that all operations - push_rear(), pop_front(), and get_min(), are performed in constant time, we will use two main data structures: a deque (double-ended queue) to store the actual elements of the queue and a secondary deque to keep track of the minimum values. The second deque helps in keeping track of the minimum value in constant time even as elements are added or removed from the queue.

Here is the approach:

  • push_rear(element): Add the element to the rear of the main deque. In the secondary deque, remove elements from the rear that are greater than the new element before adding the new element.
  • pop_front(): Remove the element from the front of both deques.
  • get_min(): Retrieve the front element of the secondary deque, which holds the minimum value of the queue.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
    private Deque<Integer> deque;
    private Deque<Integer> minDeque;

    public Solution() {
        deque = new LinkedList<>();
        minDeque = new LinkedList<>();
    }

    public void push_rear(int x) {
        deque.offerLast(x); // Queue operation
        while (!minDeque.isEmpty() && minDeque.peekLast() > x) {
            minDeque.pollLast(); // Stack operation
        }
        minDeque.offerLast(x); // Stack operation
    }

    public int pop_front() {
        if (deque.isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        int front = deque.pollFirst(); // Queue operation
        if (minDeque.peekFirst() == front) {
            minDeque.pollFirst(); // Queue operation
        }
        return front;
    }

    public int get_min() {
        if (minDeque.isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return minDeque.peekFirst(); // Stack operation acting as queue front
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def __init__(self):
        self.deque = deque()  # Main queue
        self.minDeque = deque()  # Min stack-like deque

    def push_rear(self, x: int) -> None:
        self.deque.append(x)  # Queue operation
        while self.minDeque and self.minDeque[-1] > x:
            self.minDeque.pop()  # Stack operation
        self.minDeque.append(x)  # Stack operation

    def pop_front(self) -> int:
        if not self.deque:
            raise IndexError("pop from an empty queue")
        front = self.deque.popleft()  # Queue operation
        if self.minDeque[0] == front:
            self.minDeque.popleft()  # Queue operation
        return front

    def get_min(self) -> int:
        if not self.minDeque:
            raise IndexError("min from an empty queue")
        return self.minDeque[0]  # Stack operation acting as queue front

Complexity

  • ⏰ Time complexity: O(1) for all operations (push_rear(), pop_front(), and get_min())
  • 🧺 Space complexity: O(n), where n is the number of elements in the queue since each element will occupy space in both the main deque and potentially the secondary deque.