How hard is LeetCode 1670. Design Front Middle Back Queue?

LeetCode 1670. Design Front Middle Back Queue is rated Medium on LeetCode.

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

The Python solution on this page runs in O(V+E).

What is the space complexity of LeetCode 1670. Design Front Middle Back Queue?

The Python solution on this page uses O(n), where n is the number of elements in the queue auxiliary space.

What topics does LeetCode 1670. Design Front Middle Back Queue cover?

LeetCode 1670. Design Front Middle Back Queue is tagged Design, Queue, Array, Linked List and Data Stream on LeetCode.

Design Front Middle Back Queue — LeetCode 1670 Python Solution

MediumDesignQueueArrayLinked ListData Stream

Problem: #1670
Pattern: Linked List
Reading time: 10 min
Source: leetcode.com

The problem

Design a queue that supports push and pop operations in the front, middle, and back. Implement the FrontMiddleBack class: FrontMiddleBack() Initializes the queue.

Example

Input: ["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
Output: [null, null, null, null, null, 1, 3, 4, 2, -1]
Explanation: FrontMiddleBackQueue q = new FrontMiddleBackQueue();

Python solution

Python

class FrontMiddleBackQueue:
    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

    def pushFront(self, val: int) -> None:
        self.q1.appendleft(val)
        self.rebalance()

    def pushMiddle(self, val: int) -> None:
        self.q1.append(val)
        self.rebalance()

    def pushBack(self, val: int) -> None:
        self.q2.append(val)
        self.rebalance()

    def popFront(self) -> int:
        if not self.q1 and not self.q2:
            return -1
        if self.q1:
            val = self.q1.popleft()
        else:
            val = self.q2.popleft()
        self.rebalance()
        return val

    def popMiddle(self) -> int:
        if not self.q1 and not self.q2:
            return -1
        if len(self.q1) == len(self.q2):
            val = self.q1.pop()
        else:
            val = self.q2.popleft()
        self.rebalance()
        return val

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

    def rebalance(self):
        if len(self.q1) > len(self.q2):
            self.q2.appendleft(self.q1.pop())
        if len(self.q2) > len(self.q1) + 1:
            self.q1.append(self.q2.popleft())


# Your FrontMiddleBackQueue object will be instantiated and called as such:
# obj = FrontMiddleBackQueue()
# obj.pushFront(val)
# obj.pushMiddle(val)
# obj.pushBack(val)
# param_4 = obj.popFront()
# param_5 = obj.popMiddle()
# param_6 = obj.popBack()

Complexity

Measure	Complexity
Time	O(V+E)
Space	O(n), where n is the number of elements in the queue auxiliary

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 1670. Design Front Middle Back Queue is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1670. Design Front Middle Back Queue?: LeetCode 1670. Design Front Middle Back Queue is rated Medium on LeetCode.
What is the time complexity of LeetCode 1670. Design Front Middle Back Queue?: The Python solution on this page runs in O(V+E).
What is the space complexity of LeetCode 1670. Design Front Middle Back Queue?: The Python solution on this page uses O(n), where n is the number of elements in the queue auxiliary space.
What topics does LeetCode 1670. Design Front Middle Back Queue cover?: LeetCode 1670. Design Front Middle Back Queue is tagged Design, Queue, Array, Linked List and Data Stream on LeetCode.