Facebook Pixel

1670. Design Front Middle Back Queue

MediumDesignQueueArrayLinked ListData Stream
Leetcode Link

Problem Description

This problem asks you to design a special queue data structure that supports adding and removing elements from three positions: front, middle, and back.

The FrontMiddleBackQueue class needs to implement the following operations:

  1. FrontMiddleBack(): Initialize an empty queue.

  2. pushFront(val): Add the value val to the front of the queue.

  3. pushMiddle(val): Add the value val to the middle position of the queue.

  4. pushBack(val): Add the value val to the back of the queue.

  5. popFront(): Remove and return the front element. If the queue is empty, return -1.

  6. popMiddle(): Remove and return the middle element. If the queue is empty, return -1.

  7. popBack(): Remove and return the back element. If the queue is empty, return -1.

Important rule for middle position: When the queue has an even number of elements, there are two possible middle positions. In this case, always choose the frontmost middle position.

For example:

  • If you have [1, 2, 3, 4, 5] and push 6 to the middle, it becomes [1, 2, 6, 3, 4, 5] (inserted at index 2).
  • If you have [1, 2, 3, 4, 5, 6] and pop from the middle, you remove 3 (at index 2), resulting in [1, 2, 4, 5, 6].

The solution uses two deques (q1 and q2) to efficiently handle operations at all three positions. The first deque q1 stores the first half of elements, while q2 stores the second half. A rebalance() function maintains the invariant that q2 has either the same number of elements as q1 or one more element than q1. This ensures that the middle element is always at the end of q1 (when both queues have equal length) or at the front of q2 (when q2 has one more element).

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key challenge in this problem is efficiently accessing and modifying the middle element. If we use a single array or list, pushing/popping from the front takes O(n) time, and finding the middle requires calculating the index each time.

The breakthrough comes from realizing that we can split the queue into two halves. Think of it like breaking a stick in the middle - we get two pieces that we can manipulate independently. By maintaining two separate deques, we can:

  1. Keep the front half in one deque (q1) and the back half in another (q2)
  2. The "middle" element naturally sits at the boundary between these two deques

Why does this work so well? Consider what happens with each operation:

  • Front operations only affect q1's front
  • Back operations only affect q2's back
  • Middle operations affect the boundary where q1 and q2 meet

The clever part is maintaining a balance between the two deques. We keep q2 either equal in size to q1 or having exactly one more element. This invariant means:

  • When sizes are equal: the middle is at the end of q1
  • When q2 has one extra: the middle is at the front of q2

This way, we always know exactly where the middle element is without any calculation. After each operation, we "rebalance" by moving at most one element between the deques to maintain this invariant.

The beauty of this approach is that all operations become O(1) because deques support efficient operations at both ends, and our rebalancing only ever moves a single element.

Learn more about Queue, Linked List and Data Stream patterns.

Solution Approach

The implementation uses two deques (q1 and q2) from Python's collections module to maintain the queue elements. The core idea is to split the queue into two halves and maintain a specific balance between them.

Data Structure Setup

  • q1: Stores the first half of the queue
  • q2: Stores the second half of the queue
  • Invariant: len(q2) == len(q1) or len(q2) == len(q1) + 1

The Rebalance Function

The rebalance() method maintains the balance between the two deques after each operation:

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())
  • If q1 becomes larger, move its last element to the front of q2
  • If q2 becomes too large (more than 1 element difference), move its first element to the end of q1

Push Operations

pushFront(val): Add to the front of q1, then rebalance

self.q1.appendleft(val)
self.rebalance()

pushMiddle(val): Add to the end of q1 (which is the middle position), then rebalance

self.q1.append(val)
self.rebalance()

pushBack(val): Add to the end of q2, then rebalance

self.q2.append(val)
self.rebalance()

Pop Operations

popFront():

  • If both queues are empty, return -1
  • If q1 has elements, pop from its front
  • Otherwise, pop from q2's front (when q1 is empty but q2 isn't)
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

popMiddle():

  • If both queues are empty, return -1
  • If lengths are equal, the middle is at the end of q1
  • If q2 is longer, the middle is at the front of q2
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

popBack():

  • If q2 is empty, return -1
  • Otherwise, pop from the back of q2
if not self.q2:
    return -1
val = self.q2.pop()
self.rebalance()
return val

Time Complexity

All operations run in O(1) time because:

  • Deque operations at both ends are O(1)
  • The rebalance() function moves at most one element, which is also O(1)

Space Complexity

O(n) where n is the number of elements in the queue, as we store all elements across the two deques.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a sequence of operations to see how the two-deque solution works:

Initial State: q1 = [], q2 = []

Operation 1: pushBack(1)

  • Add 1 to the back of q2: q2 = [1]
  • Rebalance: q2 has more than q1 + 1 elements, so move front of q2 to back of q1
  • Result: q1 = [1], q2 = []
  • Queue looks like: [1]

Operation 2: pushBack(2)

  • Add 2 to the back of q2: q2 = [2]
  • Rebalance: Sizes are balanced (q2 has exactly 1 more than q1)
  • Result: q1 = [1], q2 = [2]
  • Queue looks like: [1, 2]

Operation 3: pushMiddle(3)

  • Add 3 to the end of q1: q1 = [1, 3]
  • Rebalance: q1 has more elements than q2, so move last of q1 to front of q2
  • Result: q1 = [1], q2 = [3, 2]
  • Queue looks like: [1, 3, 2]

Operation 4: pushFront(4)

  • Add 4 to the front of q1: q1 = [4, 1]
  • Rebalance: Sizes are balanced
  • Result: q1 = [4, 1], q2 = [3, 2]
  • Queue looks like: [4, 1, 3, 2]

Operation 5: popMiddle()

  • Sizes are equal, so middle is at the end of q1
  • Pop from end of q1: returns 1
  • After pop: q1 = [4], q2 = [3, 2]
  • Rebalance: No change needed
  • Queue looks like: [4, 3, 2]

Operation 6: popFront()

  • q1 is not empty, so pop from front of q1: returns 4
  • After pop: q1 = [], q2 = [3, 2]
  • Rebalance: q2 has more than q1 + 1 elements, move front of q2 to back of q1
  • Result: q1 = [3], q2 = [2]
  • Queue looks like: [3, 2]

Operation 7: popBack()

  • Pop from back of q2: returns 2
  • After pop: q1 = [3], q2 = []
  • Rebalance: q1 has more elements than q2, move last of q1 to front of q2
  • Result: q1 = [], q2 = [3]
  • Queue looks like: [3]

This example demonstrates how:

  1. The two deques split the queue roughly in half
  2. The middle element sits at the boundary (end of q1 or front of q2)
  3. Rebalancing maintains the invariant after each operation
  4. All operations complete in O(1) time with at most one element moved during rebalancing

Solution Implementation

1from collections import deque
2from typing import Optional
3
4
5class FrontMiddleBackQueue:
6    """
7    A queue data structure that supports operations at front, middle, and back positions.
8    Uses two deques to maintain balance and enable O(1) middle operations.
9  
10    Invariant: len(q1) == len(q2) or len(q1) == len(q2) - 1
11    - q1 contains the front half of elements
12    - q2 contains the back half of elements
13    """
14  
15    def __init__(self) -> None:
16        """Initialize two deques to represent the front and back halves of the queue."""
17        self.front_half = deque()  # Stores front portion of the queue
18        self.back_half = deque()   # Stores back portion of the queue
19
20    def pushFront(self, val: int) -> None:
21        """
22        Add an element to the front of the queue.
23      
24        Args:
25            val: The value to be inserted at the front
26        """
27        self.front_half.appendleft(val)
28        self._rebalance()
29
30    def pushMiddle(self, val: int) -> None:
31        """
32        Add an element to the middle of the queue.
33      
34        Args:
35            val: The value to be inserted at the middle position
36        """
37        # Adding to the end of front_half puts it right at the middle
38        self.front_half.append(val)
39        self._rebalance()
40
41    def pushBack(self, val: int) -> None:
42        """
43        Add an element to the back of the queue.
44      
45        Args:
46            val: The value to be inserted at the back
47        """
48        self.back_half.append(val)
49        self._rebalance()
50
51    def popFront(self) -> int:
52        """
53        Remove and return the element from the front of the queue.
54      
55        Returns:
56            The front element, or -1 if the queue is empty
57        """
58        # Check if queue is empty
59        if not self.front_half and not self.back_half:
60            return -1
61      
62        # Pop from front_half if it exists, otherwise from back_half
63        if self.front_half:
64            result = self.front_half.popleft()
65        else:
66            result = self.back_half.popleft()
67      
68        self._rebalance()
69        return result
70
71    def popMiddle(self) -> int:
72        """
73        Remove and return the middle element from the queue.
74      
75        Returns:
76            The middle element, or -1 if the queue is empty
77        """
78        # Check if queue is empty
79        if not self.front_half and not self.back_half:
80            return -1
81      
82        # If equal lengths, middle is at the end of front_half
83        # If back_half is longer by 1, middle is at the start of back_half
84        if len(self.front_half) == len(self.back_half):
85            result = self.front_half.pop()
86        else:
87            result = self.back_half.popleft()
88      
89        self._rebalance()
90        return result
91
92    def popBack(self) -> int:
93        """
94        Remove and return the element from the back of the queue.
95      
96        Returns:
97            The back element, or -1 if the queue is empty
98        """
99        # Check if back_half is empty (queue could be empty or have only 1 element in front_half)
100        if not self.back_half:
101            return -1
102      
103        result = self.back_half.pop()
104        self._rebalance()
105        return result
106
107    def _rebalance(self) -> None:
108        """
109        Maintain the invariant that front_half and back_half differ in size by at most 1.
110        Ensures: len(front_half) == len(back_half) or len(front_half) == len(back_half) - 1
111        """
112        # If front_half has more elements, move one to back_half
113        if len(self.front_half) > len(self.back_half):
114            self.back_half.appendleft(self.front_half.pop())
115      
116        # If back_half has more than 1 extra element, move one to front_half
117        if len(self.back_half) > len(self.front_half) + 1:
118            self.front_half.append(self.back_half.popleft())
119
1class FrontMiddleBackQueue {
2    // Use two deques to maintain the queue structure
3    // q1 stores the front half, q2 stores the back half
4    // Invariant: q1.size() == q2.size() or q1.size() == q2.size() - 1
5    private Deque<Integer> frontHalf = new ArrayDeque<>();
6    private Deque<Integer> backHalf = new ArrayDeque<>();
7
8    /**
9     * Initialize the data structure
10     */
11    public FrontMiddleBackQueue() {
12    }
13
14    /**
15     * Add an element to the front of the queue
16     * @param val the value to be added
17     */
18    public void pushFront(int val) {
19        frontHalf.offerFirst(val);
20        rebalance();
21    }
22
23    /**
24     * Add an element to the middle of the queue
25     * @param val the value to be added
26     */
27    public void pushMiddle(int val) {
28        frontHalf.offerLast(val);
29        rebalance();
30    }
31
32    /**
33     * Add an element to the back of the queue
34     * @param val the value to be added
35     */
36    public void pushBack(int val) {
37        backHalf.offerLast(val);
38        rebalance();
39    }
40
41    /**
42     * Remove and return the front element of the queue
43     * @return the front element, or -1 if queue is empty
44     */
45    public int popFront() {
46        if (frontHalf.isEmpty() && backHalf.isEmpty()) {
47            return -1;
48        }
49      
50        // If front half is empty, pop from back half
51        int value = frontHalf.isEmpty() ? backHalf.pollFirst() : frontHalf.pollFirst();
52        rebalance();
53        return value;
54    }
55
56    /**
57     * Remove and return the middle element of the queue
58     * @return the middle element, or -1 if queue is empty
59     */
60    public int popMiddle() {
61        if (frontHalf.isEmpty() && backHalf.isEmpty()) {
62            return -1;
63        }
64      
65        // If sizes are equal, middle is at the end of front half
66        // Otherwise, middle is at the beginning of back half
67        int value = frontHalf.size() == backHalf.size() ? 
68                    frontHalf.pollLast() : backHalf.pollFirst();
69        rebalance();
70        return value;
71    }
72
73    /**
74     * Remove and return the back element of the queue
75     * @return the back element, or -1 if queue is empty
76     */
77    public int popBack() {
78        if (backHalf.isEmpty()) {
79            return -1;
80        }
81      
82        int value = backHalf.pollLast();
83        rebalance();
84        return value;
85    }
86
87    /**
88     * Rebalance the two deques to maintain the invariant:
89     * frontHalf.size() == backHalf.size() or frontHalf.size() == backHalf.size() - 1
90     */
91    private void rebalance() {
92        // If front half has more elements, move one to back half
93        if (frontHalf.size() > backHalf.size()) {
94            backHalf.offerFirst(frontHalf.pollLast());
95        }
96        // If back half has more than one extra element, move one to front half
97        if (backHalf.size() > frontHalf.size() + 1) {
98            frontHalf.offerLast(backHalf.pollFirst());
99        }
100    }
101}
102
103/**
104 * Your FrontMiddleBackQueue object will be instantiated and called as such:
105 * FrontMiddleBackQueue obj = new FrontMiddleBackQueue();
106 * obj.pushFront(val);
107 * obj.pushMiddle(val);
108 * obj.pushBack(val);
109 * int param_4 = obj.popFront();
110 * int param_5 = obj.popMiddle();
111 * int param_6 = obj.popBack();
112 */
113
1class FrontMiddleBackQueue {
2public:
3    FrontMiddleBackQueue() {
4        // Constructor - deques are automatically initialized as empty
5    }
6
7    void pushFront(int val) {
8        // Add element to the front of the queue
9        leftHalf.push_front(val);
10        rebalance();
11    }
12
13    void pushMiddle(int val) {
14        // Add element to the middle of the queue
15        // Push to the back of left half, then rebalance will adjust if needed
16        leftHalf.push_back(val);
17        rebalance();
18    }
19
20    void pushBack(int val) {
21        // Add element to the back of the queue
22        rightHalf.push_back(val);
23        rebalance();
24    }
25
26    int popFront() {
27        // Remove and return the front element
28        if (leftHalf.empty() && rightHalf.empty()) {
29            return -1;  // Queue is empty
30        }
31      
32        int frontValue = 0;
33        if (!leftHalf.empty()) {
34            // If left half has elements, front is at the beginning of left half
35            frontValue = leftHalf.front();
36            leftHalf.pop_front();
37        } else {
38            // If left half is empty, front is at the beginning of right half
39            frontValue = rightHalf.front();
40            rightHalf.pop_front();
41        }
42      
43        rebalance();
44        return frontValue;
45    }
46
47    int popMiddle() {
48        // Remove and return the middle element
49        if (leftHalf.empty() && rightHalf.empty()) {
50            return -1;  // Queue is empty
51        }
52      
53        int middleValue = 0;
54        if (leftHalf.size() == rightHalf.size()) {
55            // When equal sizes, middle is at the end of left half
56            middleValue = leftHalf.back();
57            leftHalf.pop_back();
58        } else {
59            // When right half is larger, middle is at the beginning of right half
60            middleValue = rightHalf.front();
61            rightHalf.pop_front();
62        }
63      
64        rebalance();
65        return middleValue;
66    }
67
68    int popBack() {
69        // Remove and return the back element
70        if (rightHalf.empty()) {
71            return -1;  // No elements in the back
72        }
73      
74        int backValue = rightHalf.back();
75        rightHalf.pop_back();
76        rebalance();
77        return backValue;
78    }
79
80private:
81    deque<int> leftHalf;   // Stores the left portion of the queue
82    deque<int> rightHalf;  // Stores the right portion of the queue
83  
84    // Maintains the invariant: leftHalf.size() <= rightHalf.size() <= leftHalf.size() + 1
85    void rebalance() {
86        // If left half has more elements than right half, move one element
87        if (leftHalf.size() > rightHalf.size()) {
88            rightHalf.push_front(leftHalf.back());
89            leftHalf.pop_back();
90        }
91      
92        // If right half has more than one extra element compared to left half, move one element
93        if (rightHalf.size() > leftHalf.size() + 1) {
94            leftHalf.push_back(rightHalf.front());
95            rightHalf.pop_front();
96        }
97    }
98};
99
100/**
101 * Your FrontMiddleBackQueue object will be instantiated and called as such:
102 * FrontMiddleBackQueue* obj = new FrontMiddleBackQueue();
103 * obj->pushFront(val);
104 * obj->pushMiddle(val);
105 * obj->pushBack(val);
106 * int param_4 = obj->popFront();
107 * int param_5 = obj->popMiddle();
108 * int param_6 = obj->popBack();
109 */
110
1// Node structure for doubly linked list
2interface Node<T> {
3    value: T;
4    next: Node<T> | null;
5    prev: Node<T> | null;
6}
7
8// Deque (Double-ended queue) implementation using doubly linked list
9interface Deque<T> {
10    front: Node<T> | null;
11    back: Node<T> | null;
12    size: number;
13}
14
15// Create a new node
16function createNode<T>(value: T): Node<T> {
17    return {
18        value: value,
19        next: null,
20        prev: null
21    };
22}
23
24// Create a new deque
25function createDeque<T>(): Deque<T> {
26    return {
27        front: null,
28        back: null,
29        size: 0
30    };
31}
32
33// Check if deque is empty
34function isDequeEmpty<T>(deque: Deque<T>): boolean {
35    return deque.size === 0;
36}
37
38// Get size of deque
39function getDequeSize<T>(deque: Deque<T>): number {
40    return deque.size;
41}
42
43// Push element to front of deque
44function pushDequeFront<T>(deque: Deque<T>, val: T): void {
45    const newNode = createNode(val);
46  
47    if (isDequeEmpty(deque)) {
48        deque.front = newNode;
49        deque.back = newNode;
50    } else {
51        newNode.next = deque.front;
52        deque.front!.prev = newNode;
53        deque.front = newNode;
54    }
55    deque.size++;
56}
57
58// Push element to back of deque
59function pushDequeBack<T>(deque: Deque<T>, val: T): void {
60    const newNode = createNode(val);
61  
62    if (isDequeEmpty(deque)) {
63        deque.front = newNode;
64        deque.back = newNode;
65    } else {
66        newNode.prev = deque.back;
67        deque.back!.next = newNode;
68        deque.back = newNode;
69    }
70    deque.size++;
71}
72
73// Pop element from front of deque
74function popDequeFront<T>(deque: Deque<T>): T | undefined {
75    if (isDequeEmpty(deque)) {
76        return undefined;
77    }
78  
79    const value = deque.front!.value;
80    deque.front = deque.front!.next;
81  
82    if (deque.front !== null) {
83        deque.front.prev = null;
84    } else {
85        deque.back = null;
86    }
87  
88    deque.size--;
89    return value;
90}
91
92// Pop element from back of deque
93function popDequeBack<T>(deque: Deque<T>): T | undefined {
94    if (isDequeEmpty(deque)) {
95        return undefined;
96    }
97  
98    const value = deque.back!.value;
99    deque.back = deque.back!.prev;
100  
101    if (deque.back !== null) {
102        deque.back.next = null;
103    } else {
104        deque.front = null;
105    }
106  
107    deque.size--;
108    return value;
109}
110
111// Global variables for FrontMiddleBackQueue
112let firstHalf: Deque<number>;
113let secondHalf: Deque<number>;
114
115// Constructor - Initialize the queue with two deques
116var FrontMiddleBackQueue = function() {
117    // First half stores the front portion of the queue
118    firstHalf = createDeque<number>();
119    // Second half stores the back portion of the queue
120    secondHalf = createDeque<number>();
121};
122
123// Rebalance the two deques to maintain the invariant:
124// size(firstHalf) <= size(secondHalf) <= size(firstHalf) + 1
125function rebalance(): void {
126    // If first half has more elements, move one to second half
127    if (getDequeSize(firstHalf) > getDequeSize(secondHalf)) {
128        const val = popDequeBack(firstHalf);
129        if (val !== undefined) {
130            pushDequeFront(secondHalf, val);
131        }
132    }
133  
134    // If second half has too many elements, move one to first half
135    if (getDequeSize(secondHalf) > getDequeSize(firstHalf) + 1) {
136        const val = popDequeFront(secondHalf);
137        if (val !== undefined) {
138            pushDequeBack(firstHalf, val);
139        }
140    }
141}
142
143// Push element to the front of the queue
144FrontMiddleBackQueue.prototype.pushFront = function(val: number): void {
145    pushDequeFront(firstHalf, val);
146    rebalance();
147};
148
149// Push element to the middle of the queue
150FrontMiddleBackQueue.prototype.pushMiddle = function(val: number): void {
151    // Push to the back of first half (which is the middle position)
152    pushDequeBack(firstHalf, val);
153    rebalance();
154};
155
156// Push element to the back of the queue
157FrontMiddleBackQueue.prototype.pushBack = function(val: number): void {
158    pushDequeBack(secondHalf, val);
159    rebalance();
160};
161
162// Pop element from the front of the queue
163FrontMiddleBackQueue.prototype.popFront = function(): number {
164    // Check if both deques are empty
165    if (isDequeEmpty(firstHalf) && isDequeEmpty(secondHalf)) {
166        return -1;
167    }
168  
169    // Pop from first half if not empty, otherwise from second half
170    const val = isDequeEmpty(firstHalf) ? popDequeFront(secondHalf) : popDequeFront(firstHalf);
171    rebalance();
172    return val !== undefined ? val : -1;
173};
174
175// Pop element from the middle of the queue
176FrontMiddleBackQueue.prototype.popMiddle = function(): number {
177    // Check if both deques are empty
178    if (isDequeEmpty(firstHalf) && isDequeEmpty(secondHalf)) {
179        return -1;
180    }
181  
182    // If sizes are equal, pop from back of first half; otherwise from front of second half
183    const val = getDequeSize(firstHalf) === getDequeSize(secondHalf) 
184        ? popDequeBack(firstHalf) 
185        : popDequeFront(secondHalf);
186    rebalance();
187    return val !== undefined ? val : -1;
188};
189
190// Pop element from the back of the queue
191FrontMiddleBackQueue.prototype.popBack = function(): number {
192    // Check if second half is empty
193    if (isDequeEmpty(secondHalf)) {
194        return -1;
195    }
196  
197    const val = popDequeBack(secondHalf);
198    rebalance();
199    return val !== undefined ? val : -1;
200};
201
202/**
203 * Your FrontMiddleBackQueue object will be instantiated and called as such:
204 * var obj = new FrontMiddleBackQueue()
205 * obj.pushFront(val)
206 * obj.pushMiddle(val)
207 * obj.pushBack(val)
208 * var param_4 = obj.popFront()
209 * var param_5 = obj.popMiddle()
210 * var param_6 = obj.popBack()
211 */
212

Time and Space Complexity

Time Complexity: O(1) for all operations (pushFront, pushMiddle, pushBack, popFront, popMiddle, popBack)

Each operation performs a constant number of deque operations:

  • pushFront: Performs appendleft() on q1 and calls rebalance() - both O(1)
  • pushMiddle: Performs append() on q1 and calls rebalance() - both O(1)
  • pushBack: Performs append() on q2 and calls rebalance() - both O(1)
  • popFront: Performs either popleft() on q1 or q2 and calls rebalance() - both O(1)
  • popMiddle: Performs either pop() on q1 or popleft() on q2 and calls rebalance() - both O(1)
  • popBack: Performs pop() on q2 and calls rebalance() - both O(1)

The rebalance() method performs at most two deque operations (pop()/popleft() and append()/appendleft()), which are all O(1) operations in Python's deque implementation.

Space Complexity: O(n), where n is the total number of elements in the queue

The space is used to store all elements across two deques (q1 and q2). The total space required is proportional to the number of elements stored, with no additional auxiliary space needed beyond the storage of the elements themselves.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Middle Position Calculation When Queue is Empty or Has One Element

A common mistake is not properly handling edge cases when the queue is empty or contains only one element, particularly in the popMiddle() and popFront() operations.

Pitfall Example:

def popMiddle(self) -> int:
    # WRONG: Doesn't check if queue is completely empty
    if len(self.front_half) == len(self.back_half):
        return self.front_half.pop()  # Fails if front_half is empty
    else:
        return self.back_half.popleft()  # Fails if back_half is empty

Solution: Always check if the entire queue is empty before attempting any pop operation:

def popMiddle(self) -> int:
    if not self.front_half and not self.back_half:
        return -1
    # Rest of the logic...

2. Forgetting to Rebalance After Operations

The rebalancing step is crucial to maintain the invariant that the two deques differ by at most one element. Forgetting to call _rebalance() after push or pop operations will break the middle position logic.

Pitfall Example:

def pushFront(self, val: int) -> None:
    self.front_half.appendleft(val)
    # WRONG: Missing rebalance call
    # This could make front_half much larger than back_half

Solution: Always call _rebalance() after every modification:

def pushFront(self, val: int) -> None:
    self.front_half.appendleft(val)
    self._rebalance()  # Essential to maintain invariant

3. Incorrect Rebalancing Logic

The rebalancing function must handle both cases: when front_half is too large AND when back_half is too large. A common mistake is only handling one direction or using the wrong comparison.

Pitfall Example:

def _rebalance(self) -> None:
    # WRONG: Using 'elif' instead of separate 'if' statements
    if len(self.front_half) > len(self.back_half):
        self.back_half.appendleft(self.front_half.pop())
    elif len(self.back_half) > len(self.front_half) + 1:  # This might not execute when needed
        self.front_half.append(self.back_half.popleft())

Solution: Use two separate if statements to handle both imbalance cases:

def _rebalance(self) -> None:
    if len(self.front_half) > len(self.back_half):
        self.back_half.appendleft(self.front_half.pop())
    if len(self.back_half) > len(self.front_half) + 1:
        self.front_half.append(self.back_half.popleft())

4. Wrong Middle Element Selection for Even-Length Queues

When the queue has an even number of elements, the problem specifies choosing the frontmost middle position. This means for a queue like [1, 2, 3, 4], the middle should be at index 1 (value 2), not index 2.

Pitfall Example:

def popMiddle(self) -> int:
    # WRONG: Incorrect logic for determining middle position
    if len(self.back_half) > len(self.front_half):
        return self.back_half.popleft()
    else:
        return self.front_half.pop()  # Wrong condition

Solution: The correct logic is:

  • When lengths are equal: middle is at the end of front_half
  • When back_half is longer by 1: middle is at the front of back_half
def popMiddle(self) -> int:
    if not self.front_half and not self.back_half:
        return -1
    if len(self.front_half) == len(self.back_half):
        return self.front_half.pop()
    else:  # len(back_half) = len(front_half) + 1
        return self.back_half.popleft()

5. Not Handling Single Element Queue in popFront()

When the queue has only one element (stored in back_half due to the invariant), popFront() must retrieve it from back_half, not front_half.

Pitfall Example:

def popFront(self) -> int:
    if not self.front_half:
        return -1  # WRONG: Ignores element in back_half
    return self.front_half.popleft()

Solution: Check both deques and handle the case where front_half is empty but back_half isn't:

def popFront(self) -> int:
    if not self.front_half and not self.back_half:
        return -1
    if self.front_half:
        result = self.front_half.popleft()
    else:  # front_half is empty but back_half has one element
        result = self.back_half.popleft()
    self._rebalance()
    return result
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What data structure does Breadth-first search typically uses to store intermediate states?

Recommended Readings

Queue Intro

Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

Median of Data Stream

Median of Data Stream Given a stream of numbers find the median number at any given time accurate to 1 decimal place Example add_number 1 add_number 2 add_number 3 get_median 2 0 add_number 4 get_median 2 5 Try it yourself Explanation Intuition Brute force way is to sort the entire list every time we get a new number This would be O N log N for each add_number operation One step up is to notice that the list is sorted before we add any new number to it So every

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More