How do you solve Design Front Middle Back Queue on LeetCode?

Design Front Middle Back Queue (LeetCode #1670) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(1) for each operation time complexity and O(n) space complexity. Key insight: Using two deques allows for efficient middle operations by balancing the sizes of the two halves.

What is the brute force solution for Design Front Middle Back Queue?

The brute force approach for Design Front Middle Back Queue is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach uses a single list to store all elements and performs operations directly on that list. This is simple to implement but can be inefficient for certain operations, especially when inserting or removing elements from the middle. The optimal Optimal Solution approach improves this to O(1) for each operation.

What are the interview tips for Design Front Middle Back Queue?

Explain your thought process clearly when designing the data structure. Consider edge cases, such as operations on an empty queue. Be prepared to discuss the trade-offs of your chosen approach.

What are common mistakes when solving Design Front Middle Back Queue?

Not balancing the two halves after each operation, which can lead to incorrect middle element retrieval. Confusing the middle element logic when the sizes of the two halves are equal.

#1670

Design Front Middle Back Queue

Medium

ArrayLinked ListDesignQueueDoubly-Linked ListData StreamDequeTwo-pointer technique

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(1) for each operation
Space	O(1)	O(n)

💡

Intuition

Time O(1) for each operationSpace O(n)

The optimal solution uses two double-ended queues (deques) to efficiently manage the front and back halves of the queue. This allows O(1) time complexity for all operations by balancing the two deques based on their sizes.

⚙️

Algorithm

3 steps

1Step 1: Use two deques, one for the front half and one for the back half of the queue.
2Step 2: For push operations, add elements to the appropriate deque and balance them if necessary.
3Step 3: For pop operations, remove elements from the appropriate deque and balance them if necessary.

solution.py45 lines

1from collections import deque
2
3class FrontMiddleBackQueue:
4    def __init__(self):
5        self.front = deque()
6        self.back = deque()
7
8    def pushFront(self, val):
9        self.front.appendleft(val)
10        self.balance()
11
12    def pushMiddle(self, val):
13        if len(self.front) > len(self.back):
14            self.back.appendleft(self.front.pop())
15        self.front.append(val)
16        self.balance()
17
18    def pushBack(self, val):
19        self.back.append(val)
20        self.balance()
21
22    def popFront(self):
23        if not self.front and not self.back:
24            return -1
25        if self.front:
26            return self.front.popleft()
27        return self.back.popleft()
28
29    def popMiddle(self):
30        if not self.front and not self.back:
31            return -1
32        if len(self.front) > len(self.back):
33            return self.front.pop()
34        return self.back.popleft()
35
36    def popBack(self):
37        if not self.back:
38            return -1
39        return self.back.pop()
40
41    def balance(self):
42        if len(self.front) > len(self.back) + 1:
43            self.back.appendleft(self.front.pop())
44        elif len(self.back) > len(self.front):
45            self.front.append(self.back.popleft())

ℹ

Complexity note: The time complexity is O(1) for each operation because we are only adding or removing elements from the front or back of the deques, which is efficient. The space complexity is O(n) because we store all elements in two deques.

1Using two deques allows for efficient middle operations by balancing the sizes of the two halves.
2When the total number of elements is even, the middle is defined as the frontmost middle element.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.