Design Front Middle Back Queue

Medium

Asked by:

6 views

Topics:

Linked Lists

Design a queue that supports push and pop operations in the front, middle, and back.

Implement the FrontMiddleBack class:

FrontMiddleBack() Initializes the queue.
void pushFront(int val) Adds val to the front of the queue.
void pushMiddle(int val) Adds val to the middle of the queue.
void pushBack(int val) Adds val to the back of the queue.
int popFront() Removes the front element of the queue and returns it. If the queue is empty, return -1.
int popMiddle() Removes the middle element of the queue and returns it. If the queue is empty, return -1.
int popBack() Removes the back element of the queue and returns it. If the queue is empty, return -1.

Notice that when there are two middle position choices, the operation is performed on the frontmost middle position choice. For example:

Pushing 6 into the middle of [1, 2, 3, 4, 5] results in [1, 2, 6, 3, 4, 5].
Popping the middle from [1, 2, 3, 4, 5, 6] returns 3 and results in [1, 2, 4, 5, 6].

Example 1:

Input:
["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
[[], [1], [2], [3], [4], [], [], [], [], []]
Output:
[null, null, null, null, null, 1, 3, 4, 2, -1]

Explanation:
FrontMiddleBackQueue q = new FrontMiddleBackQueue();
q.pushFront(1);   // [1]
q.pushBack(2);    // [1, 2]
q.pushMiddle(3);  // [1, 3, 2]
q.pushMiddle(4);  // [1, 4, 3, 2]
q.popFront();     // return 1 -> [4, 3, 2]
q.popMiddle();    // return 3 -> [4, 2]
q.popMiddle();    // return 4 -> [2]
q.popBack();      // return 2 -> []
q.popFront();     // return -1 -> [] (The queue is empty)

Constraints:

1 <= val <= 10⁹
At most 1000 calls will be made to pushFront, pushMiddle, pushBack, popFront, popMiddle, and popBack.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

To be precise about the 'middle' element for a queue of size `n`, should `pushMiddle` insert at index `n / 2`, and `popMiddle` remove from index `(n - 1) / 2`?
The pop operations are specified to return -1 when the queue is empty. Is it guaranteed that -1 will not be pushed as a valid element into the queue, or should I handle this potential ambiguity?
Could you confirm the behavior for the edge case of a single-element queue? For instance, if the queue is `[10]`, does `popMiddle` correctly remove and return `10`?
Regarding the overall design, are there any concurrency requirements? In other words, should the implementation be thread-safe?
The constraints mention at most 1000 calls, which might allow for linear-time operations to pass. Is the goal to find the most optimal solution, ideally with constant-time complexity for all operations?

Brute Force Solution

Approach

The brute force approach is to store all the numbers in a single, simple line. Whenever we need to add or remove an item from the front or the middle, we manually shift all the other numbers around to make space or close a gap.

Here's how the algorithm would work step-by-step:

Imagine all the items are kept in one continuous, ordered line.
To add an item to the back, simply place it at the very end of the line.
To add an item to the front, you must first slide every single item in the line one position over to make an empty spot at the beginning, then place the new item there.
To add an item to the middle, first find the middle point of the line. Then, slide every item from the middle to the end one position over to create a gap, and then insert the new item into that gap.
To remove an item from the back, just take the last one off the end of the line.
To remove an item from the front, take the first one away. This leaves a hole, so you must then slide all the remaining items forward to close the gap.
To remove an item from the middle, find the middle point and take that item out. This also leaves a hole, so you have to slide all the items that came after it forward to fill the empty spot.
Before any removal, if the line is empty to begin with, there is nothing to do.

Code Implementation

class FrontMiddleBackQueue:
    def __init__(self):
        # A single list is used to represent the queue, as described by the brute-force approach.

        self.queue_data = []

    def pushFront(self, value_to_add):
        # Inserting at index 0 forces all other elements to shift right, creating space at the front.

        self.queue_data.insert(0, value_to_add)

    def pushMiddle(self, value_to_add):
        # The insertion point is len // 2, which places the new element just before the original middle.

        middle_index = len(self.queue_data) // 2
        self.queue_data.insert(middle_index, value_to_add)

    def pushBack(self, value_to_add):
        self.queue_data.append(value_to_add)

    def popFront(self):
        if not self.queue_data:
            return -1
        return self.queue_data.pop(0)

    def popMiddle(self):
        if not self.queue_data:
            return -1

        # The middle element to pop is at index (n-1)//2 to correctly handle both even and odd lengths.

        number_of_elements = len(self.queue_data)
        middle_index = (number_of_elements - 1) // 2
        return self.queue_data.pop(middle_index)

    def popBack(self):
        if not self.queue_data:
            return -1
        return self.queue_data.pop()

Big(O) Analysis

Time Complexity

O(n) – The runtime complexity is driven by operations that require shifting elements within the single continuous line. Let n be the number of items in the queue. For operations like pushFront or popFront, every single one of the n elements must be moved to either create or close a gap at the beginning. Similarly, pushMiddle and popMiddle require shifting approximately half the elements, which is n/2 operations, to insert or remove an item. Since the number of required shifts is directly proportional to the total number of elements n in the worst case, the time complexity is O(n).

Space Complexity

O(N) – The brute force approach uses a single data structure, described as a 'continuous, ordered line,' to store all the elements of the queue. Let N be the number of items currently in this line. The memory required for this underlying data structure, such as a list or dynamic array, is directly proportional to N. All described shifting operations to add or remove elements are performed in-place on this single structure, using no significant extra memory. Therefore, the total space complexity is determined by the storage for the N elements, resulting in O(N).

Optimal Solution

Approach

The core strategy is to split the entire collection into two smaller, manageable halves: a front part and a back part. By keeping these two parts nearly the same size, we ensure that the front, back, and the 'middle' are always immediately accessible, avoiding the need to search through the whole collection.

Here's how the algorithm would work step-by-step:

Think of the queue as being managed by two separate containers, one holding the front half of the items and the other holding the back half.
Establish a balancing rule: the front container can have the same number of items as the back one, or just one more, but never any other size difference. This keeps the true 'middle' right between the two containers.
To add an item to the very front or very back, place it in the corresponding container.
After any addition, check if the containers are still balanced. If one has become too large, move the item closest to the center from the larger container to the smaller one to restore balance.
To add an item to the middle, always place it at the end of the front container. Then, perform the same balancing check.
To remove an item from the very front or very back, simply take it from the correct container.
After any removal, the containers might become unbalanced. If so, move an item from the larger container to the smaller one to fix it.
Thanks to our balancing rule, the middle item is always the last one in the front container. To remove it, just take that item and then rebalance the two containers if necessary.

Code Implementation

from collections import deque

class FrontMiddleBackQueue:
    def __init__(self):
        self.left_half = deque()
        self.right_half = deque()

    def _rebalance(self):
        # This ensures the left half has at most one more element than the right, our key invariant.

        if len(self.left_half) > len(self.right_half) + 1:
            element_to_move = self.left_half.pop()
            self.right_half.appendleft(element_to_move)
        elif len(self.left_half) < len(self.right_half):
            element_to_move = self.right_half.popleft()
            self.left_half.append(element_to_move)

    def pushFront(self, new_value):
        self.left_half.appendleft(new_value)
        self._rebalance()

    def pushMiddle(self, new_value):
        # If the left side is larger, we must move an element to the right to make room for the new middle.

        if len(self.left_half) > len(self.right_half):
            element_to_move = self.left_half.pop()
            self.right_half.appendleft(element_to_move)
        self.left_half.append(new_value)

    def pushBack(self, new_value):
        self.right_half.append(new_value)
        self._rebalance()

    def popFront(self):
        if not self.left_half:
            return -1
        
        popped_value = self.left_half.popleft()
        # After any removal, we must rebalance to maintain quick access to the middle element.

        self._rebalance()
        return popped_value

    def popMiddle(self):
        if not self.left_half:
            return -1

        popped_value = self.left_half.pop()
        self._rebalance()
        return popped_value

    def popBack(self):
        # The last element could be in the left half if the queue is small, so we must check the right half first.

        if not self.right_half:
            if not self.left_half:
                return -1
            return self.popMiddle()
        
        popped_value = self.right_half.pop()
        self._rebalance()
        return popped_value

Big(O) Analysis

Time Complexity

O(1) – The time complexity for each individual operation is O(1). This efficiency is achieved by using two deques, which allows for constant-time access and modifications to the front, middle, and back elements. Any operation, such as pushing to the middle or popping from the front, requires at most a few actions on the ends of these two deques. The crucial rebalancing step, which is occasionally needed, only involves moving a single element from one deque to the other, a constant time task that is not dependent on n, the total number of elements.

Space Complexity

O(N) – The solution's space complexity is determined by the two containers used to manage the front and back halves of the queue. Let N be the total number of elements in the queue at any given time. These two containers must collectively store all N elements. Therefore, the memory usage is directly proportional to the number of items being held. The rebalancing operations described only require a constant amount of extra space for temporary variables, which does not affect the overall linear space complexity.

Edge Cases

Case	How to Handle
Calling any pop operation on a completely empty queue.	The implementation must check if the queue is empty at the beginning of each pop method and return -1 as required.
Calling `popBack` on a queue containing just one element.	The code must correctly retrieve the element from the left deque since the right deque will be empty in this specific scenario.
Using `pushMiddle` on a queue with an odd number of elements.	The implementation must shift the left deque's last element to the right deque before pushing the new middle element to the left deque.
A pop operation that unbalances the deques, for example making the right deque larger than the left.	A rebalancing function must be called to move an element from the right deque to the left deque to restore the size invariant.
A `popFront` operation that makes the left deque more than one element smaller than the right one.	The solution must rebalance by moving an element from the right deque's front to the left deque's back to maintain correct structure.
Popping the middle element from a queue with an even number of elements.	The solution must correctly pop the last element of the left deque, which corresponds to the frontmost middle position.
A sequence of operations that grows the queue and then shrinks it back to empty.	The state of the two internal deques must be managed correctly to handle transitions from empty, to non-empty, and back to empty again.
The number of operations is large, approaching the specified maximum of 1000.	The two-deque approach provides O(1) time complexity for all operations, ensuring the solution remains performant and avoids a timeout.

Calling any pop operation on a completely empty queue.

How to Handle:

The implementation must check if the queue is empty at the beginning of each pop method and return -1 as required.

Calling `popBack` on a queue containing just one element.

How to Handle:

The code must correctly retrieve the element from the left deque since the right deque will be empty in this specific scenario.

Using `pushMiddle` on a queue with an odd number of elements.

How to Handle:

The implementation must shift the left deque's last element to the right deque before pushing the new middle element to the left deque.

A pop operation that unbalances the deques, for example making the right deque larger than the left.

How to Handle:

A rebalancing function must be called to move an element from the right deque to the left deque to restore the size invariant.

A `popFront` operation that makes the left deque more than one element smaller than the right one.

How to Handle:

The solution must rebalance by moving an element from the right deque's front to the left deque's back to maintain correct structure.

Popping the middle element from a queue with an even number of elements.

How to Handle:

The solution must correctly pop the last element of the left deque, which corresponds to the frontmost middle position.

A sequence of operations that grows the queue and then shrinks it back to empty.

How to Handle:

The state of the two internal deques must be managed correctly to handle transitions from empty, to non-empty, and back to empty again.

The number of operations is large, approaching the specified maximum of 1000.

How to Handle:

The two-deque approach provides O(1) time complexity for all operations, ensuring the solution remains performant and avoids a timeout.