Design Front Middle Back Queue — Two Deques (LeetCode 1670)

Design Front Middle Back Queue (LeetCode 1670) requires implementing a queue that supports push and pop operations at the front, middle, and back — all efficiently. The key insight is splitting the data across two deques and keeping them balanced.

The Problem

Implement FrontMiddleBackQueue with these operations:

• pushFront(val) — add to the front
• pushMiddle(val) — add to the middle (left-middle if even length)
• pushBack(val) — add to the back
• popFront() — remove and return the front element
• popMiddle() — remove and return the middle element
• popBack() — remove and return the back element

Return -1 if the queue is empty for any pop operation.

pushFront(1): [1]
pushBack(2):  [1, 2]
pushMiddle(3): [1, 3, 2]
pushMiddle(4): [1, 4, 3, 2]
popFront() → 1: [4, 3, 2]
popMiddle() → 3: [4, 2]
popBack() → 2: [4]

Approach: Two Balanced Deques

Split the elements between a left deque and a right deque:

Full queue: [a, b, c, d, e]

Left deque:  [a, b]      (first half)
Right deque: [c, d, e]   (second half, includes middle if odd)

Balance invariant: len(right) == len(left) or len(right) == len(left) + 1.

This means the middle element is always at the boundary between the two deques.

Implementation

from collections import deque

class FrontMiddleBackQueue:
    """
    Two-deque approach for front/middle/back operations.
    All operations are O(1) amortized.
    """
    def __init__(self):
        self.left = deque()   # first half
        self.right = deque()  # second half (>=left in size)

    def _balance(self):
        """Maintain: len(right) == len(left) or len(left) + 1."""
        if len(self.right) > len(self.left) + 1:
            # right too big → move front of right to back of left
            self.left.append(self.right.popleft())
        elif len(self.left) > len(self.right):
            # left too big → move back of left to front of right
            self.right.appendleft(self.left.pop())

    def pushFront(self, val: int) -> None:
        self.left.appendleft(val)
        self._balance()

    def pushMiddle(self, val: int) -> None:
        # If even total length, insert at left-middle
        if len(self.left) == len(self.right):
            self.right.appendleft(val)
        else:
            self.left.append(val)
        # No rebalance needed — we inserted at the boundary

    def pushBack(self, val: int) -> None:
        self.right.append(val)
        self._balance()

    def popFront(self) -> int:
        if not self.left and not self.right:
            return -1
        if self.left:
            val = self.left.popleft()
        else:
            val = self.right.popleft()
        self._balance()
        return val

    def popMiddle(self) -> int:
        if not self.left and not self.right:
            return -1
        if len(self.left) == len(self.right):
            # Even total: middle is last of left
            val = self.left.pop()
        else:
            # Odd total: middle is first of right
            val = self.right.popleft()
        self._balance()
        return val

    def popBack(self) -> int:
        if not self.right:
            return -1
        val = self.right.pop()
        self._balance()
        return val

Step-by-Step Trace

Operation        left          right         Queue View
──────────────────────────────────────────────────────────
pushFront(1)     []            [1]           [1]
pushBack(2)      [1]           [2]           [1, 2]
pushMiddle(3)    [1]           [3, 2]        [1, 3, 2]
pushMiddle(4)    [1, 4]        [3, 2]        [1, 4, 3, 2]

popFront()→1     [4]           [3, 2]        [4, 3, 2]
  left.popleft()=1, rebalance: len(right)=2 > len(left)+1=2? No

popMiddle()→3    [4]           [2]           [4, 2]
  odd total (3): right.popleft()=3

popMiddle()→4    []            [2]           [2]
  even total (2): left.pop()=4

popBack()→2      []            []            []
  right.pop()=2

popFront()→-1    empty!

The Balance Function in Detail

The rebalancing logic is simple but critical:

def _balance(self):
    # Case 1: right has 2+ more than left
    # Move right's front to left's back
    if len(self.right) > len(self.left) + 1:
        self.left.append(self.right.popleft())

    # Case 2: left has more than right
    # Move left's back to right's front
    elif len(self.left) > len(self.right):
        self.right.appendleft(self.left.pop())

After every push/pop, calling _balance() restores the invariant. Since at most one element moves, it is O(1).

Why Two Deques?

Approach	pushFront	pushMiddle	pushBack	popMiddle
Array	O(n)	O(n)	O(1)	O(n)
Linked List	O(1)	O(n)	O(1)	O(n)
Two Deques	O(1)	O(1)	O(1)	O(1)

The two-deque approach gives O(1) for all six operations.

Complexity Analysis

Operation	Time	Space
pushFront	O(1)	O(1)
pushMiddle	O(1)	O(1)
pushBack	O(1)	O(1)
popFront	O(1)	O(1)
popMiddle	O(1)	O(1)
popBack	O(1)	O(1)
Total space	—	O(n)

Edge Cases

q = FrontMiddleBackQueue()

# Pop from empty queue
assert q.popFront() == -1
assert q.popMiddle() == -1
assert q.popBack() == -1

# Single element
q.pushBack(42)
assert q.popMiddle() == 42  # middle of [42] is 42

# Two elements — middle is left-middle
q.pushBack(1); q.pushBack(2)
assert q.popMiddle() == 1  # [1, 2] → middle is index 0

# All operations interleaved
q2 = FrontMiddleBackQueue()
q2.pushFront(1)
q2.pushBack(3)
q2.pushMiddle(2)  # [1, 2, 3]
assert q2.popBack() == 3
assert q2.popFront() == 1
assert q2.popMiddle() == 2

When to Use This Pattern

Use the two-deque split pattern when:

• You need O(1) access to the middle of a sequence
• The problem requires push/pop at both ends and middle
• You need to maintain a balanced split of data

This pattern also works for median-finding with two heaps and for sliding window median problems.

Common Mistakes

1. Wrong middle definition — for even length, LeetCode uses the left-middle (floor division)
2. Forgetting to rebalance after every operation
3. Handling single element — when left is empty, the element is in right
4. Off-by-one in pushMiddle — depends on whether total is even or odd

Related Problems

Problem	Key Difference
Design Circular Deque (LC 641)	No middle operations
Find Median from Data Stream (LC 295)	Two heaps, similar balancing
Sliding Window Median (LC 480)	Two sorted sets
Design Circular Queue (LC 622)	Fixed size, no middle

Key Takeaways

• Splitting a queue into two balanced deques enables O(1) middle access
• The invariant len(right) = len(left) or len(right) = len(left) + 1 keeps the middle at the boundary
• Rebalancing after each operation moves at most one element — O(1)
• This pattern is a building block for many “design a data structure” interview questions