Design Front Middle Back Queue - Solution & Explanation

Q: Is Design Front Middle Back Queue easy or hard?

Design Front Middle Back Queue is classified as a Medium problem on LeetCode. The difficulty comes from maintaining the correct middle position while supporting constant-time operations. Once the idea of splitting the queue into two balanced halves is understood, the implementation becomes straightforward.

Q: Design Front Middle Back Queue Python/Java solution

Python solutions usually rely on collections.deque to maintain two balanced halves for constant-time operations. Java implementations often use a custom doubly linked list or two Deque objects such as ArrayDeque. Both approaches maintain O(1) time for push and pop operations at all three positions.

Q: How to solve Design Front Middle Back Queue in O(1)?

Split the queue into two deques representing the left and right halves. Maintain the invariant that the left deque size is either equal to the right deque size or exactly one larger. Perform operations on the appropriate deque and rebalance by moving a single element between them if needed, ensuring each operation stays O(1).

Q: What is the best approach for Design Front Middle Back Queue?

The most common solution uses two balanced deques. One deque stores the left half of the queue and the other stores the right half, while maintaining the invariant that the left side has either the same number of elements or one extra. This makes the middle position the boundary between the two structures, allowing all operations—push and pop at front, middle, and back—to run in O(1) time.

Q: Is Design Front Middle Back Queue asked at Google/Amazon/Meta?

Problems that require designing custom queues with additional operations frequently appear in interviews at large tech companies. Variants of queue design and double-ended data structures have been reported in interviews at companies like Amazon and Google because they test both data structure intuition and implementation skills.

Q: What data structure is used in Design Front Middle Back Queue?

Two primary structures work well: double-ended queues (deques) or a doubly linked list with a tracked middle pointer. The deque solution relies on maintaining two balanced halves, while the linked list version updates head, tail, and middle pointers after each operation.

Q: What is the time complexity of Design Front Middle Back Queue?

With the optimal design, every operation runs in O(1) time. The deque-based approach performs constant-time insertions and removals at both ends, and rebalancing moves at most one element between the two halves. Space complexity is O(n) because all elements must be stored.

MediumArray Linked List Design Queue27 min readAsked at: Amazon, Google, Citadel

Practice this problem

Problem Statement

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

Implement the FrontMiddleBack class:

FrontMiddleBack() 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, return -1.
int popMiddle() Removes the middle element of the queue and returns it. If the queue is empty, return -1.
int popBack() Removes the back element of the queue and returns it. If the queue is empty, return -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] returns 3 and results in [1, 2, 4, 5, 6].

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:
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 -> [] (The queue is empty)

Constraints:

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

Approach Overview

Problem Overview: Design a queue that supports insertion and deletion from three positions: the front, the middle, and the back. The data structure must expose operations like pushFront, pushMiddle, pushBack, and their corresponding pop operations while keeping the middle definition consistent as elements change.

Approach 1: Deque Based Approach (O(1) time, O(n) space)

The cleanest solution splits the queue into two balanced halves using two deque structures: left and right. The invariant is that left.size() is either equal to right.size() or exactly one larger. Front operations interact with the front of left, back operations interact with the end of right, and middle operations insert or remove from the boundary between them. After every operation, you rebalance by moving one element between the deques if the size difference breaks the invariant. Because deque operations like append, appendleft, pop, and popleft run in constant time, every queue operation also runs in O(1) time with O(n) space for stored elements.

This approach is practical in languages with efficient deque implementations such as Python and JavaScript. Conceptually it behaves like maintaining the left half and right half of the queue separately, which makes the "middle" position simply the boundary between them. It relies heavily on properties of a queue and efficient double-ended operations.

Approach 2: Linked List Based Approach (O(1) time, O(n) space)

A lower-level implementation uses a doubly linked list with explicit pointers to the head, tail, and middle node. Each insertion or deletion updates the relevant pointer and then adjusts the middle pointer depending on whether the size of the list becomes even or odd. For example, when inserting near the front while the size becomes odd, the middle pointer may move one step backward. When removing elements, similar pointer adjustments maintain the correct middle node.

This design mirrors how queues can be implemented from scratch without relying on built‑in containers. Every operation touches only a constant number of nodes and pointer updates, so the runtime remains O(1). Space usage is O(n) for the nodes themselves. It is a good exercise in pointer manipulation and fits naturally with classic design and data stream style problems.

Recommended for interviews: The two-deque solution is typically the expected answer. It demonstrates the key insight: keep the queue split into balanced halves so the middle element is always easy to access. A linked list version shows strong understanding of pointer-based data structures, but the deque approach communicates the idea faster and is easier to implement correctly under interview pressure.

Approach 1: Deque Based Approach

This approach utilizes two separate deques (or double-ended queues) to manage the elements efficiently. One deque manages the left half of the queue and the other manages the right half.

For operations concerning the front, we utilize the front of the left deque. For back operations, we utilize the back of the right deque.

For middle operations, we ensure that the deques remain balanced or have at most a one-element difference. The 'middle' element is the last element of the left deque when both deques have equal size, or the first element of the right deque otherwise.

Balancing the two deques efficiently allows you to perform middle operations in constant amortized time.

The implementation utilizes two deques from the Python standard library to efficiently manage operations at the front, middle, and back. By maintaining two separate deques for the left and right segments of the queue, the solution is able to balance the elements by moving elements between the deques when necessary.

The balance method ensures that the sizes of the deques differ by at most one, which is crucial for correct middle element operations.

Code

Python JavaScript

Python

JavaScript

Complexity

Time Complexity: The time complexity for each operation is O(1) due to the efficient re-balancing of the deques.
Space Complexity: O(N), where N is the number of elements in the queue.

Try this approach in the editor →

Approach 2: Linked List Based Approach

This approach uses a doubly linked list to implement the queue, which allows efficient insertion and deletion from both ends and from the middle.

By keeping a pointer/reference to the middle node, operations that involve the middle element can be performed in constant time. The challenge is to keep the middle pointer updated correctly as elements are added or removed.

This design achieves a consistent constant time complexity for all operations, though it requires careful handling of pointers due to frequent updates, especially in middle operations.

The C++ implementation uses a doubly linked list to manage the queue elements. Each node has pointers to its previous and next nodes, allowing for efficient insertion and removal from any position.

The solution maintains a pointer to the middle element, updating it as necessary to reflect changes in the list structure. This approach handles list elements in a highly flexible manner, supporting the required operations in constant time.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(1) for each operation, due to the efficient handling of linked list pointers and constant time updates of the middle node.
Space Complexity: O(N), where N is the number of elements in the queue.

Try this approach in the editor →

Approach 3: Two Deques

We use two deques, where q_1 stores the first half, and q_2 stores the second half. The rebalance function is used to maintain the balance between the two queues, i.e., keeping the length of q_2 greater than or equal to the length of q_1, and the difference in length does not exceed 1.

In the pushFront, pushMiddle, and pushBack functions, we only need to add elements to q_1 or q_2, and call the rebalance function.

For the popFront function, we need to check whether q_1 and q_2 are empty. If both are empty, return -1. Otherwise, we need to check whether q_1 is empty. If not, pop the front element of q_1, otherwise pop the front element of q_2, and call the rebalance function.

For the popMiddle function, we need to check whether q_1 and q_2 are empty. If both are empty, return -1. Otherwise, we need to check whether the lengths of q_1 and q_2 are equal. If they are equal, pop the last element of q_1, otherwise pop the front element of q_2, and call the rebalance function.

For the popBack function, we only need to check whether q_2 is empty. If it is empty, return -1. Otherwise, pop the last element of q_2, and call the rebalance function.

The time complexity of the above operations is O(1), and the space complexity is O(n), where n is the number of elements in the queue.

Code

Python Java C++Go TypeScript JavaScript

Python

Java

C++

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Deque Based Approach	Time Complexity: The time complexity for each operation is O(1) due to the efficient re-balancing of the deques. Space Complexity: O(N), where N is the number of elements in the queue.
Linked List Based Approach	Time Complexity: O(1) for each operation, due to the efficient handling of linked list pointers and constant time updates of the middle node. Space Complexity: O(N), where N is the number of elements in the queue.
Two Deques	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Two Deques (Balanced Halves)	O(1) per operation	O(n)	Best practical solution when a language provides efficient deque operations
Doubly Linked List with Middle Pointer	O(1) per operation	O(n)	Useful when implementing custom data structures or practicing pointer manipulation

Video Solution

Leetcode 1670. Design Front Middle Back Queue • Fraz • 2,522 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Design Front Middle Back Queue easy or hard?

Design Front Middle Back Queue is classified as a Medium problem on LeetCode. The difficulty comes from maintaining the correct middle position while supporting constant-time operations. Once the idea of splitting the queue into two balanced halves is understood, the implementation becomes straightforward.

Design Front Middle Back Queue Python/Java solution

Python solutions usually rely on collections.deque to maintain two balanced halves for constant-time operations. Java implementations often use a custom doubly linked list or two Deque objects such as ArrayDeque. Both approaches maintain O(1) time for push and pop operations at all three positions.

How to solve Design Front Middle Back Queue in O(1)?

Split the queue into two deques representing the left and right halves. Maintain the invariant that the left deque size is either equal to the right deque size or exactly one larger. Perform operations on the appropriate deque and rebalance by moving a single element between them if needed, ensuring each operation stays O(1).

What is the best approach for Design Front Middle Back Queue?

The most common solution uses two balanced deques. One deque stores the left half of the queue and the other stores the right half, while maintaining the invariant that the left side has either the same number of elements or one extra. This makes the middle position the boundary between the two structures, allowing all operations—push and pop at front, middle, and back—to run in O(1) time.

Is Design Front Middle Back Queue asked at Google/Amazon/Meta?

Problems that require designing custom queues with additional operations frequently appear in interviews at large tech companies. Variants of queue design and double-ended data structures have been reported in interviews at companies like Amazon and Google because they test both data structure intuition and implementation skills.

What data structure is used in Design Front Middle Back Queue?

Two primary structures work well: double-ended queues (deques) or a doubly linked list with a tracked middle pointer. The deque solution relies on maintaining two balanced halves, while the linked list version updates head, tail, and middle pointers after each operation.

What is the time complexity of Design Front Middle Back Queue?

With the optimal design, every operation runs in O(1) time. The deque-based approach performs constant-time insertions and removals at both ends, and rebalancing moves at most one element between the two halves. Space complexity is O(n) because all elements must be stored.

Ready to solve this problem?

Practice Design Front Middle Back Queue with our built-in code editor and test cases.

Practice on FleetCode

Design Circular Deque

Design Circular Queue

Problem Info

DifficultyMedium

Acceptance58.5%

Approaches3

Reading time27 min

Asked at

Amazon Google Citadel

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Deque Based Approach

Code

Complexity

Approach 2: Linked List Based Approach

Code

Complexity

Approach 3: Two Deques

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents