LeetCode 1670 - Design Front Middle Back Queue

LeetCode Problem 1670

Difficulty: 🟡 Medium
Topics: Array, Linked List, Design, Queue, Doubly-Linked List, Data Stream

Solution

Problem Understanding

The problem is asking us to design a specialized queue that allows insertions and removals not only at the front and back, but also at the middle of the queue. We need to maintain the queue such that we can efficiently access and modify elements at these three positions. The middle operation is slightly tricky because when the queue has an even number of elements, the "middle" is defined as the frontmost of the two middle positions.

The input consists of a sequence of operations (pushFront, pushMiddle, pushBack, popFront, popMiddle, popBack) along with integer values for push operations. The expected output is the result of pop operations, returning -1 if the queue is empty. The constraints indicate that the maximum number of operations is 1000 and values are between 1 and $10^9$. This is a moderate size, allowing linear-time operations, but optimal solutions are preferred for clarity and efficiency.

Important edge cases include pushing or popping when the queue is empty, handling even versus odd length queues when determining the middle element, and ensuring proper ordering when elements are pushed to the middle.

Approaches

The brute-force approach is to maintain the queue as a simple Python list (or Go slice) and perform insertions or deletions at the specified indices. For pushFront or popFront, we would use index 0, for pushBack or popBack, we would use the last index, and for middle operations, we compute the middle index based on the current length. This works correctly, but list insertions and deletions in the middle require O(n) time, which is inefficient if the queue grows large.

The key insight for an optimal solution is to use two balanced deques to represent the front and back halves of the queue. By keeping the front half and back half roughly equal in size, we can achieve O(1) amortized operations for push and pop at the front, middle, and back. Whenever an imbalance occurs (difference of sizes greater than 1), we rebalance the two halves. This method uses a double-ended queue (deque) data structure, which allows efficient insertion and deletion from both ends.

Algorithm Walkthrough

1. Initialize two deques: front and back. The front deque will store the first half of the elements, and back will store the second half.
2. For pushFront(val), insert val at the left end of front and then rebalance.
3. For pushBack(val), append val at the right end of back and then rebalance.
4. For pushMiddle(val), if front has more elements than back, move the last element of front to the left of back. Then append val to the right end of front.
5. For popFront(), remove and return the leftmost element from front. If front is empty, remove from back. Then rebalance.
6. For popBack(), remove and return the rightmost element from back. If back is empty, remove from front. Then rebalance.
7. For popMiddle(), if front has the same number or one more element than back, remove from the right of front. Otherwise, remove from the left of back. Then rebalance.
8. Rebalance ensures that the size difference between front and back is at most 1 by moving elements from one deque to another as needed.

Why it works: By splitting the queue into two halves and maintaining the size invariant, we can efficiently access the middle element, which is always at the end of front if the total size is odd or balanced. All operations manipulate either the ends of the deques, which is O(1) in Python.

Python Solution

from collections import deque

class FrontMiddleBackQueue:

    def __init__(self):
        self.front = deque()
        self.back = deque()
        
    def _rebalance(self):
        while len(self.front) > len(self.back) + 1:
            self.back.appendleft(self.front.pop())
        while len(self.front) < len(self.back):
            self.front.append(self.back.popleft())

    def pushFront(self, val: int) -> None:
        self.front.appendleft(val)
        self._rebalance()

    def pushMiddle(self, val: int) -> None:
        if len(self.front) > len(self.back):
            self.back.appendleft(self.front.pop())
        self.front.append(val)

    def pushBack(self, val: int) -> None:
        self.back.append(val)
        self._rebalance()

    def popFront(self) -> int:
        if not self.front and not self.back:
            return -1
        if self.front:
            val = self.front.popleft()
        else:
            val = self.back.popleft()
        self._rebalance()
        return val

    def popMiddle(self) -> int:
        if not self.front and not self.back:
            return -1
        if len(self.front) >= len(self.back):
            val = self.front.pop()
        else:
            val = self.back.popleft()
        self._rebalance()
        return val

    def popBack(self) -> int:
        if not self.front and not self.back:
            return -1
        if self.back:
            val = self.back.pop()
        else:
            val = self.front.pop()
        self._rebalance()
        return val

Implementation Explanation: The front and back deques split the queue logically. The _rebalance method ensures that front never has more than one element than back and never fewer. Push and pop operations always manipulate the ends of these deques, allowing constant time operations.

Go Solution

package main

type FrontMiddleBackQueue struct {
    front []int
    back  []int
}

func Constructor() FrontMiddleBackQueue {
    return FrontMiddleBackQueue{
        front: []int{},
        back:  []int{},
    }
}

func (this *FrontMiddleBackQueue) rebalance() {
    for len(this.front) > len(this.back)+1 {
        this.back = append([]int{this.front[len(this.front)-1]}, this.back...)
        this.front = this.front[:len(this.front)-1]
    }
    for len(this.front) < len(this.back) {
        this.front = append(this.front, this.back[0])
        this.back = this.back[1:]
    }
}

func (this *FrontMiddleBackQueue) PushFront(val int) {
    this.front = append([]int{val}, this.front...)
    this.rebalance()
}

func (this *FrontMiddleBackQueue) PushMiddle(val int) {
    if len(this.front) > len(this.back) {
        this.back = append([]int{this.front[len(this.front)-1]}, this.back...)
        this.front = this.front[:len(this.front)-1]
    }
    this.front = append(this.front, val)
}

func (this *FrontMiddleBackQueue) PushBack(val int) {
    this.back = append(this.back, val)
    this.rebalance()
}

func (this *FrontMiddleBackQueue) PopFront() int {
    if len(this.front) == 0 && len(this.back) == 0 {
        return -1
    }
    var val int
    if len(this.front) > 0 {
        val = this.front[0]
        this.front = this.front[1:]
    } else {
        val = this.back[0]
        this.back = this.back[1:]
    }
    this.rebalance()
    return val
}

func (this *FrontMiddleBackQueue) PopMiddle() int {
    if len(this.front) == 0 && len(this.back) == 0 {
        return -1
    }
    var val int
    if len(this.front) >= len(this.back) {
        val = this.front[len(this.front)-1]
        this.front = this.front[:len(this.front)-1]
    } else {
        val = this.back[0]
        this.back = this.back[1:]
    }
    this.rebalance()
    return val
}

func (this *FrontMiddleBackQueue) PopBack() int {
    if len(this.front) == 0 && len(this.back) == 0 {
        return -1
    }
    var val int
    if len(this.back) > 0 {
        val = this.back[len(this.back)-1]
        this.back = this.back[:len(this.back)-1]
    } else {
        val = this.front[len(this.front)-1]
        this.front = this.front[:len(this.front)-1]
    }
    this.rebalance()
    return val
}

Go-Specific Notes: Since Go slices do not have an efficient popFront, we use slice operations carefully. We prepend with append([]int{val}, slice...) and slice for removal. The logic otherwise mirrors the Python deque-based approach.

Worked Examples

Using the example from the problem statement: