We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Design Front Middle Back Queue

Number: 1767

Difficulty: Medium

Paid? No

Companies: Citadel, Meta, Amazon

Problem Description

Design a queue that supports insertion and deletion operations at the front, middle, and back. The twist is that when operating on the middle in an even-sized queue, the operation is performed on the left middle element.

Key Insights

  • Use two deques (or similar data structures) to maintain the two halves of the queue.
  • Always keep the left half either equal in size to or one element larger than the right half.
  • Inserting or removing in the middle becomes equivalent to manipulating the end of the left deque.
  • After every operation, rebalance the deques to maintain the invariant.

Space and Time Complexity

Time Complexity: O(1) amortized per operation, as deque operations and rebalancing steps are constant time. Space Complexity: O(n), where n is the number of elements in the queue.

Solution

We can implement the Front Middle Back Queue using two deques (or dynamic arrays) called left and right. The idea is to store the first half of the elements in left and the latter half in right so that the middle element is always at the end of left.

For push operations:

  • pushFront: Add the element to the front of left, then rebalance.
  • pushMiddle: Insert the element at the end of left if sizes are equal, or move an element from left to right to maintain the invariant and then insert.
  • pushBack: Add the element to the back of right, then rebalance.

For pop operations:

  • popFront: Remove from the front of left if not empty; if left is empty but right is not, adjust accordingly.
  • popMiddle: Remove the last element from left as it represents the front middle.
  • popBack: Remove from the back of right if possible, otherwise remove from left.

After each operation, balance the two halves by ensuring that left has at most one more element than right. This strategy allows O(1) amortized operations.

Code Solutions

from collections import deque

class FrontMiddleBackQueue:
    def __init__(self):
        # left deque: stores the first half (or one more than right)
        # right deque: stores the second half
        self.left = deque()
        self.right = deque()
    
    def rebalance(self):
        # Ensure left deque has equal or one more element than right deque.
        if len(self.left) > len(self.right) + 1:
            # Move the last element of left to the front of right.
            self.right.appendleft(self.left.pop())
        elif len(self.left) < len(self.right):
            # Move the first element of right to the end of left.
            self.left.append(self.right.popleft())
    
    def pushFront(self, val: int) -> None:
        self.left.appendleft(val)
        self.rebalance()
    
    def pushMiddle(self, val: int) -> None:
        # If left size equals right, insert at end of left.
        if len(self.left) == len(self.right):
            self.left.append(val)
        else:
            # Otherwise move the last element of left to right, then add the new element into left.
            self.right.appendleft(self.left.pop())
            self.left.append(val)
        self.rebalance()
    
    def pushBack(self, val: int) -> None:
        self.right.append(val)
        self.rebalance()
    
    def popFront(self) -> int:
        if not self.left and not self.right:
            return -1
        # If left is empty, then adjust accordingly.
        if self.left:
            val = self.left.popleft()
        else:
            val = self.right.popleft()
        self.rebalance()
        return val
    
    def popMiddle(self) -> int:
        if not self.left and not self.right:
            return -1
        # Middle is always the last element of left.
        val = self.left.pop()
        self.rebalance()
        return val
    
    def popBack(self) -> int:
        if not self.left and not self.right:
            return -1
        if self.right:
            val = self.right.pop()
        else:
            # All elements in left.
            val = self.left.pop()
        self.rebalance()
        return val

# Example usage:
# q = FrontMiddleBackQueue()
# q.pushFront(1)
# q.pushBack(2)
# q.pushMiddle(3)
# q.pushMiddle(4)
# print(q.popFront())   # returns 1
# print(q.popMiddle())  # returns 3
# print(q.popMiddle())  # returns 4
# print(q.popBack())    # returns 2
# print(q.popFront())   # returns -1 if empty
← Back to All Questions