Design Front Middle Back Queue — Problem & Solution
Design Front Middle Back Queue solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Design Front Middle Back Queue is a medium coding problem on arrays and queue.
- Difficulty: Medium
- Topics: Arrays, Queue
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Design a queue that can add and remove elements at the front, the back and the middle.
Write the class FrontMiddleBackQueue:
FrontMiddleBackQueue()creates an empty queue.void pushFront(int value),void pushMiddle(int value)andvoid pushBack(int value)insertvalueat the front, the middle and the back.int popFront(),int popMiddle()andint popBack()remove the element at the front, the middle and the back and return it, or return-1if the queue is empty.
When there are two middle positions, the operation uses the one nearer the front. For example, pushMiddle(6) on [1,2,3,4,5] gives [1,2,6,3,4,5], and popMiddle() on [1,2,6,3,4,5] removes and returns 6.
The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.
Example 1
Input: ["FrontMiddleBackQueue","pushFront","pushBack","pushMiddle","pushMiddle","popFront","popMiddle","popMiddle","popBack","popFront"]
[[],[1],[2],[3],[4],[],[],[],[],[]]
Output: [null,null,null,null,null,1,3,4,2,-1]
Explanation: The queue becomes [1], [1,2], [1,3,2], then [1,4,3,2]. popFront takes 1 leaving [4,3,2]; popMiddle takes the middle 3; on [4,2] the front middle is 4; popBack takes 2, and the empty queue gives -1.
Example 2
Input: ["FrontMiddleBackQueue","pushBack","pushBack","pushBack","pushBack","pushBack","pushMiddle","popMiddle","popMiddle"]
[[],[10],[20],[30],[40],[50],[60],[],[]]
Output: [null,null,null,null,null,null,null,60,30]
Explanation: [10,20,30,40,50] has one middle position for an insertion, before 30: [10,20,60,30,40,50]. popMiddle on six elements takes the front middle, 60, and on five elements the true middle, 30.
Constraints
1 <= value <= 10^9At most 1000 calls are made to the six methods in total
Hints for Design Front Middle Back Queue
Hint 1
With one array the middle operations shift half the elements every time. Can you keep the middle at an end of something?
Hint 2
Split the queue into a front half and a back half, each a deque, and keep the back half equal in size to the front half or one larger.
Hint 3
Then the front middle for popping is the last of the front half when the halves are equal, and the first of the back half otherwise; inserting in the middle goes to the front of the back half when equal, the back of the front half otherwise. After any front/back operation, move one element across to restore the balance.
How to solve Design Front Middle Back Queue
Keep two deques, left and right, whose concatenation is the queue, with len(left) <= len(right) <= len(left) + 1. The middle is then always at the seam, so every operation touches only deque ends.
Approach
rebalance(): ifleftis longer thanright, move the last ofleftto the front ofright; ifrightis two longer thanleft, move the first ofrightto the back ofleft.pushFront: add to the front ofleft, rebalance.pushBack: add to the back ofright, rebalance.pushMiddle: if the halves are equal, add to the front ofright; otherwise add to the back ofleft.- Pops on an empty queue (
rightempty) return -1.popFront: take the front ofleft, or ofrightifleftis empty, then rebalance.popBack: take the back ofright, rebalance. popMiddle: if the halves are equal take the back ofleft, otherwise the front ofright.
Why it works
For a queue of size n, insertion in the middle means position floor(n/2) and removal means index floor((n-1)/2). With the invariant, left holds exactly the first floor(n/2) elements, so position floor(n/2) is the seam: the front of right when n is even, the back of left when odd keeps the sizes legal. Index floor((n-1)/2) is the last of left when n is even and the first of right when it is odd. Each operation changes the sizes by one, and one move across restores the invariant.
Complexity
- Time —
O(1) per call - Space —
O(n)
Pitfalls
- Off by one in the middle rules: insertion goes to index
n/2, removal takes index(n-1)/2, both rounded down. - With one element it sits in
right;popFrontmust look there whenleftis empty. - A plain list with insert/remove at the middle also passes 1000 calls, at O(n) each.
Reference solution
Python
from collections import deque
class FrontMiddleBackQueue:
def __init__(self):
self.left = deque() # invariant: len(left) <= len(right) <= len(left) + 1
self.right = deque()
def _balance(self):
if len(self.left) > len(self.right):
self.right.appendleft(self.left.pop())
elif len(self.right) > len(self.left) + 1:
self.left.append(self.right.popleft())
def pushFront(self, value: int) -> None:
self.left.appendleft(value)
self._balance()
def pushMiddle(self, value: int) -> None:
if len(self.left) == len(self.right):
self.right.appendleft(value)
else:
self.left.append(value)
def pushBack(self, value: int) -> None:
self.right.append(value)
self._balance()
def popFront(self) -> int:
if not self.right:
return -1
x = self.left.popleft() if self.left else self.right.popleft()
self._balance()
return x
def popMiddle(self) -> int:
if not self.right:
return -1
if len(self.left) == len(self.right):
return self.left.pop()
return self.right.popleft()
def popBack(self) -> int:
if not self.right:
return -1
x = self.right.pop()
self._balance()
return xJava
class FrontMiddleBackQueue {
// invariant: left.size() <= right.size() <= left.size() + 1
private Deque<Integer> left = new ArrayDeque<>(), right = new ArrayDeque<>();
public FrontMiddleBackQueue() {
}
private void balance() {
if (left.size() > right.size()) right.addFirst(left.pollLast());
else if (right.size() > left.size() + 1) left.addLast(right.pollFirst());
}
public void pushFront(int value) {
left.addFirst(value);
balance();
}
public void pushMiddle(int value) {
if (left.size() == right.size()) right.addFirst(value); else left.addLast(value);
}
public void pushBack(int value) {
right.addLast(value);
balance();
}
public int popFront() {
if (right.isEmpty()) return -1;
int x = left.isEmpty() ? right.pollFirst() : left.pollFirst();
balance();
return x;
}
public int popMiddle() {
if (right.isEmpty()) return -1;
return left.size() == right.size() ? left.pollLast() : right.pollFirst();
}
public int popBack() {
if (right.isEmpty()) return -1;
int x = right.pollLast();
balance();
return x;
}
}C++
class FrontMiddleBackQueue {
deque<int> left, right; // invariant: left.size() <= right.size() <= left.size() + 1
void balance() {
if (left.size() > right.size()) { right.push_front(left.back()); left.pop_back(); }
else if (right.size() > left.size() + 1) { left.push_back(right.front()); right.pop_front(); }
}
public:
FrontMiddleBackQueue() {}
void pushFront(int value) {
left.push_front(value);
balance();
}
void pushMiddle(int value) {
if (left.size() == right.size()) right.push_front(value); else left.push_back(value);
}
void pushBack(int value) {
right.push_back(value);
balance();
}
int popFront() {
if (right.empty()) return -1;
int x;
if (left.empty()) { x = right.front(); right.pop_front(); }
else { x = left.front(); left.pop_front(); }
balance();
return x;
}
int popMiddle() {
if (right.empty()) return -1;
int x;
if (left.size() == right.size()) { x = left.back(); left.pop_back(); }
else { x = right.front(); right.pop_front(); }
return x;
}
int popBack() {
if (right.empty()) return -1;
int x = right.back();
right.pop_back();
balance();
return x;
}
};JavaScript
var FrontMiddleBackQueue = function() {
this.left = []; // invariant: left.length <= right.length <= left.length + 1
this.right = [];
};
FrontMiddleBackQueue.prototype.balance = function() {
if (this.left.length > this.right.length) this.right.unshift(this.left.pop());
else if (this.right.length > this.left.length + 1) this.left.push(this.right.shift());
};
FrontMiddleBackQueue.prototype.pushFront = function(value) {
this.left.unshift(value);
this.balance();
};
FrontMiddleBackQueue.prototype.pushMiddle = function(value) {
if (this.left.length === this.right.length) this.right.unshift(value);
else this.left.push(value);
};
FrontMiddleBackQueue.prototype.pushBack = function(value) {
this.right.push(value);
this.balance();
};
FrontMiddleBackQueue.prototype.popFront = function() {
if (this.right.length === 0) return -1;
var x = this.left.length ? this.left.shift() : this.right.shift();
this.balance();
return x;
};
FrontMiddleBackQueue.prototype.popMiddle = function() {
if (this.right.length === 0) return -1;
return this.left.length === this.right.length ? this.left.pop() : this.right.shift();
};
FrontMiddleBackQueue.prototype.popBack = function() {
if (this.right.length === 0) return -1;
var x = this.right.pop();
this.balance();
return x;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Queues and Deques