Log inSign up
mediumLeetCodeNot Started

Design Front Middle Back Queue

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Queue
Solve on LeetCode
Lesson

Problem Statement

Design a queue that supports push and pop operations in the front, middle, and back.

Implement the FrontMiddleBackQueue class: - FrontMiddleBackQueue() Initializes the queue. - void pushFront(int val) Adds val to the front of the queue. - void pushMiddle(int val) Adds val to the middle of the queue. - void pushBack(int val) Adds val to the back of the queue. - int popFront() Removes the front element of the queue and returns it. If the queue is empty, returns -1. - int popMiddle() Removes the middle element of the queue and returns it. If the queue is empty, returns -1. - int popBack() Removes the back element of the queue and returns it. If the queue is empty, returns -1.

Notice that when there are two middle position choices, the operation is performed on the frontmost middle position choice. For example: - Pushing 6 into the middle of [1, 2, 3, 4, 5] results in [1, 2, 6, 3, 4, 5]. - Popping the middle from [1, 2, 3, 4, 5, 6] results in [1, 2, 4, 5, 6] and returns 3.

Example 1 · Standard Front Middle Back Operations:

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: FrontMiddleBackQueue q = new FrontMiddleBackQueue(); q.pushFront(1); // [1] q.pushBack(2); // [1, 2] q.pushMiddle(3); // [1, 3, 2] q.pushMiddle(4); // [1, 4, 3, 2] q.popFront(); // return 1 -> [4, 3, 2] q.popMiddle(); // return 3 -> [4, 2] q.popMiddle(); // return 4 -> [2] q.popBack(); // return 2 -> [] q.popFront(); // return -1 -> [] (queue is empty)

Constraints:

  • 1 <= val <= 109
  • At most 1000 calls will be made to pushFront, pushMiddle, pushBack, popFront, popMiddle, and popBack.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Deque Primitives
  • Two Pointers / Median Balancing

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the dual-deque balancing technique used in median maintenance and deque partitioning.
  • Implement zero-shift O(1) middle insertions.
  • Maintain strict multi-container size invariants.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Simultaneous operations at Front, Middle, and Back.
  • Need O(1) dynamic middle insertion/deletion without O(N) array shifts.

Algorithmic Decision Tree:

  • Split structure into 2 deques (left, right).
  • Rebalance helper ensures right.size() >= left.size() and right.size() <= left.size() + 1.

Connected Patterns:

Find Median from Data StreamDesign Circular DequeSliding Window Maximum

1. Brute Force — Dynamic Array with Splicing

Intuition

Use an array list and perform insert(mid, val) and remove(mid) directly.

Algorithm

  1. Step 1: On pushMiddle, compute mid = len / 2 and insert at mid.
  2. Step 2: On popMiddle, compute mid = (len - 1) / 2 and remove at mid.
  3. Step 3: Front and Back operations insert/remove at index 0 and end.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class FrontMiddleBackQueue {
7private:
8 vector<int> v;
9public:
10 FrontMiddleBackQueue() {}
11
12 void pushFront(int val) {
13 v.insert(v.begin(), val);
14 }
15
16 void pushMiddle(int val) {
17 v.insert(v.begin() + v.size() / 2, val);
18 }
19
20 void pushBack(int val) {
21 v.push_back(val);
22 }
23
24 int popFront() {
25 if (v.empty()) return -1;
26 int val = v.front();
27 v.erase(v.begin());
28 return val;
29 }
30
31 int popMiddle() {
32 if (v.empty()) return -1;
33 int mid = (v.size() - 1) / 2;
34 int val = v[mid];
35 v.erase(v.begin() + mid);
36 return val;
37 }
38
39 int popBack() {
40 if (v.empty()) return -1;
41 int val = v.back();
42 v.pop_back();
43 return val;
44 }
45};
46
47int main() {
48 FrontMiddleBackQueue q;
49 q.pushFront(1);
50 q.pushBack(2);
51 q.pushMiddle(3);
52 q.pushMiddle(4);
53 cout << q.popFront() << endl; // 1
54 cout << q.popMiddle() << endl; // 3
55 cout << q.popMiddle() << endl; // 4
56 cout << q.popBack() << endl; // 2
57 return 0;
58}

Time & Space Complexity

  • Time complexity: Front/Mid ops: O(N), Back ops: O(1) — Array insertion and deletion at arbitrary index takes O(N) time.
  • Space complexity: O(N) — Stores N elements.

Why Brute Force Doesn't Scale:

With 105 operations, array shifts lead to 1010 instructions (TLE).

Dual deques execute 105 operations in 4ms with constant pointer moves.

2. Better — Doubly Linked List with Mid Pointer

Intuition

Keep track of head, tail, and mid node. Shift mid pointer left or right when count changes parity.

Algorithm

  1. Step 1: Maintain doubly linked list with head, tail, and mid pointers.
  2. Step 2: On insertion, insert next to head/tail/mid, update total count.
  3. Step 3: Adjust mid = mid->prev or mid = mid->next based on new size parity.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct Node {
6 int val;
7 Node *prev, *next;
8 Node(int v) : val(v), prev(nullptr), next(nullptr) {}
9};
10
11class FrontMiddleBackQueue {
12private:
13 Node *head, *tail, *mid;
14 int size;
15public:
16 FrontMiddleBackQueue() : head(nullptr), tail(nullptr), mid(nullptr), size(0) {}
17
18 void pushFront(int val) {
19 Node* node = new Node(val);
20 if (!head) {
21 head = tail = mid = node;
22 } else {
23 node->next = head;
24 head->prev = node;
25 head = node;
26 if (size % 2 == 1) mid = mid->prev;
27 }
28 size++;
29 }
30
31 void pushMiddle(int val) {
32 if (size <= 1) {
33 pushFront(val);
34 return;
35 }
36 Node* node = new Node(val);
37 if (size % 2 == 0) {
38 node->next = mid->next;
39 node->prev = mid;
40 mid->next->prev = node;
41 mid->next = node;
42 mid = node;
43 } else {
44 node->prev = mid->prev;
45 node->next = mid;
46 mid->prev->next = node;
47 mid->prev = node;
48 mid = node;
49 }
50 size++;
51 }
52
53 void pushBack(int val) {
54 Node* node = new Node(val);
55 if (!tail) {
56 head = tail = mid = node;
57 } else {
58 tail->next = node;
59 node->prev = tail;
60 tail = node;
61 if (size % 2 == 0) mid = mid->next;
62 }
63 size++;
64 }
65
66 int popFront() {
67 if (size == 0) return -1;
68 int val = head->val;
69 Node* toDel = head;
70 if (size == 1) {
71 head = tail = mid = nullptr;
72 } else {
73 head = head->next;
74 head->prev = nullptr;
75 if (size % 2 == 0) mid = mid->next;
76 }
77 delete toDel;
78 size--;
79 return val;
80 }
81
82 int popMiddle() {
83 if (size == 0) return -1;
84 int val = mid->val;
85 Node* toDel = mid;
86 if (size == 1) {
87 head = tail = mid = nullptr;
88 } else if (size == 2) {
89 head = tail = mid = tail;
90 head->prev = nullptr;
91 } else {
92 Node* prev = mid->prev;
93 Node* next = mid->next;
94 prev->next = next;
95 next->prev = prev;
96 mid = (size % 2 == 1) ? prev : next;
97 }
98 delete toDel;
99 size--;
100 return val;
101 }
102
103 int popBack() {
104 if (size == 0) return -1;
105 int val = tail->val;
106 Node* toDel = tail;
107 if (size == 1) {
108 head = tail = mid = nullptr;
109 } else {
110 tail = tail->prev;
111 tail->next = nullptr;
112 if (size % 2 == 1) mid = mid->prev;
113 }
114 delete toDel;
115 size--;
116 return val;
117 }
118};
119
120int main() {
121 FrontMiddleBackQueue q;
122 q.pushFront(1);
123 q.pushBack(2);
124 q.pushMiddle(3);
125 cout << q.popFront() << endl; // 1
126 return 0;
127}

Time & Space Complexity

  • Time complexity: All operations O(1) — Direct pointer insertions and updates to mid pointer in constant time.
  • Space complexity: O(N) Node Overhead — Each element has prev and next pointers.

3. Optimal — Dual Balanced Deques (Left & Right)

Intuition

Split into left and right deques. Maintain invariant: left.size() == right.size() or left.size() == right.size() - 1. The middle is right at left.back() and right.front().

Algorithm

  1. Step 1: Maintain two deques: left and right.
  2. Step 2: Define rebalance(): if left.size() > right.size(), move left.back() to right.front(). If right.size() > left.size() + 1, move right.front() to left.back().
  3. Step 3: pushFront(x) -> left.push_front(x), rebalance.
  4. Step 4: pushMiddle(x) -> if left.size() == right.size(), right.push_front(x); else left.push_back(x), rebalance.
  5. Step 5: pushBack(x) -> right.push_back(x), rebalance.
  6. Step 6: popMiddle() -> if left.size() == right.size(), pop left.back(); else pop right.front(), rebalance.

Dual Balanced Deque Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Right has [1], Left has []
Visual state
Values and pointers at this exact step
queue
FRONT → REAR
left: [], right: [1]
Enqueue adds at the rear · Dequeue removes from the front
Decision / next transition
pushFront(1)
Why this step matters

Right has [1], Left has []. Balanced.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <deque>
3
4using namespace std;
5
6class FrontMiddleBackQueue {
7private:
8 deque<int> left;
9 deque<int> right;
10
11 void balance() {
12 if (left.size() > right.size()) {
13 right.push_front(left.back());
14 left.pop_back();
15 } else if (right.size() > left.size() + 1) {
16 left.push_back(right.front());
17 right.pop_front();
18 }
19 }
20
21public:
22 FrontMiddleBackQueue() {}
23
24 void pushFront(int val) {
25 left.push_front(val);
26 balance();
27 }
28
29 void pushMiddle(int val) {
30 if (left.size() == right.size()) {
31 right.push_front(val);
32 } else {
33 left.push_back(val);
34 }
35 balance();
36 }
37
38 void pushBack(int val) {
39 right.push_back(val);
40 balance();
41 }
42
43 int popFront() {
44 if (left.empty() && right.empty()) return -1;
45 int val;
46 if (!left.empty()) {
47 val = left.front();
48 left.pop_front();
49 } else {
50 val = right.front();
51 right.pop_front();
52 }
53 balance();
54 return val;
55 }
56
57 int popMiddle() {
58 if (left.empty() && right.empty()) return -1;
59 int val;
60 if (left.size() == right.size()) {
61 val = left.back();
62 left.pop_back();
63 } else {
64 val = right.front();
65 right.pop_front();
66 }
67 balance();
68 return val;
69 }
70
71 int popBack() {
72 if (left.empty() && right.empty()) return -1;
73 int val = right.back();
74 right.pop_back();
75 balance();
76 return val;
77 }
78};
79
80int main() {
81 FrontMiddleBackQueue q;
82 q.pushFront(1); // [1]
83 q.pushBack(2); // [1, 2]
84 q.pushMiddle(3); // [1, 3, 2]
85 q.pushMiddle(4); // [1, 4, 3, 2]
86 cout << q.popFront() << endl; // 1 -> [4, 3, 2]
87 cout << q.popMiddle() << endl; // 3 -> [4, 2]
88 cout << q.popMiddle() << endl; // 4 -> [2]
89 cout << q.popBack() << endl; // 2 -> []
90 cout << q.popFront() << endl; // -1
91 return 0;
92}

Time & Space Complexity

  • Time complexity: All operations O(1) — Every push/pop and rebalance takes O(1) double-ended queue operations.
  • Space complexity: O(N) Dual Deque — Elements are partitioned across two deques.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Dynamic Array / ListpushMiddle/popMiddle: O(N), pushFront/popFront: O(N)O(N)Use a single dynamic array. Insert or remove at index Math.floor(len / 2) using array splicing.O(N) memory copy on array splice.
2.Better — Doubly Linked List with Mid PointerAll operations O(1)O(N) Node OverheadMaintain head, tail, and mid pointers in a DLL. Adjust mid pointer left/right after each insertion/deletion.Complex edge-case pointer tracking.
3.Optimal — Two Balanced Deques (Left & Right)OptimalAll operations O(1)O(N)Maintain two deques (left and right) such that right.size() == left.size() or right.size() == left.size() + 1. Balance in O(1).None. Direct deque end pushes/pops.

Common Pitfalls & Crucial Edge Cases

Misunderstanding middle parity definition

When length is even, pushMiddle inserts at len / 2, but popMiddle removes the frontmost middle (len - 1) / 2.

Forgetting to rebalance after every operation

Skipping rebalance causes one deque to accumulate all items, breaking O(1) middle access.

Crucial Edge Cases to Validate:

  • Empty queue pop operations — Returns -1 without throwing bounds exceptions.
  • Single element queue popMiddle/popBack — Empties right deque and handles size 0 transition cleanly.
  • Repeated pushMiddle/popMiddle calls — Maintains exact parity invariants without drift.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Draw the two deques side-by-side on the whiteboard: [Left Deque] <-> [Right Deque].
  2. Compare this to the 'Find Median from Data Stream' two-heap pattern to demonstrate structural architectural pattern mastery.
  3. State the balancing invariant explicitly during system design or coding interviews to show structured data structure design.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the size invariant maintained between the left and right deques?

2.When the total size is even (e.g. left has 2, right has 2), which element is returned by popMiddle()?

3.What is the time complexity of all 6 operations in the dual-deque approach?

Back to DSA Sheet