1670. Design Front Middle Back Queue
On LeetCode ->Problem¶
Design a queue supporting insertion and removal at the front, middle, and back. Empty removals return -1.
For length \(n\), insert the middle at index \(\lfloor n/2 \rfloor\); remove it at index \(\lfloor (n-1)/2 \rfloor\).
Operation Return Queue
pushBack(1) None [1]
pushBack(2) None [1, 2]
pushMiddle(3) None [1, 3, 2]
pushMiddle(4) None [1, 4, 3, 2]
popMiddle() 4 [1, 3, 2]
popMiddle() 3 [1, 2]
class FrontMiddleBackQueue:
def __init__(self):
pass
def pushFront(self, val: int) -> None:
pass
def pushMiddle(self, val: int) -> None:
pass
def pushBack(self, val: int) -> None:
pass
def popFront(self) -> int:
pass
def popMiddle(self) -> int:
pass
def popBack(self) -> int:
pass
Key trick¶
Use two deques: the left half has either the same number of elements as the right half or one more, making the removable middle always the last element of the left half.
Trap¶
Middle insertion and removal use different indices for even lengths; insertion into an odd-length queue must happen before its current middle.
Why is it interesting?¶
A size invariant turns an interior operation into an endpoint operation, giving constant-time access without maintaining linked-list pointers.
Python solution¶
from collections import deque
class FrontMiddleBackQueue:
def __init__(self):
# Queue order: left followed by right.
# Invariant: len(left) - len(right) is either 0 or 1.
self.left = deque()
self.right = deque()
def _balance(self) -> None:
# Each operation changes the imbalance by at most two.
if len(self.left) > len(self.right) + 1:
self.right.appendleft(self.left.pop())
elif len(self.left) < len(self.right):
self.left.append(self.right.popleft())
def pushFront(self, val: int) -> None:
self.left.appendleft(val)
self._balance()
def pushMiddle(self, val: int) -> None:
# For odd lengths, insert before the existing middle.
if len(self.left) > len(self.right):
self.right.appendleft(self.left.pop())
self.left.append(val)
def pushBack(self, val: int) -> None:
self.right.append(val)
self._balance()
def popFront(self) -> int:
if not self.left:
return -1
val = self.left.popleft()
self._balance()
return val
def popMiddle(self) -> int:
if not self.left:
return -1
val = self.left.pop()
self._balance()
return val
def popBack(self) -> int:
if not self.left:
return -1
# A singleton lives in left, with right empty.
val = self.right.pop() if self.right else self.left.pop()
self._balance()
return val
Time: \(O(1)\) per operation. Space: \(O(n)\) for \(n\) stored elements.
Comment on my solution¶
Your doubly linked list can achieve \(O(1)\) operations, but its middle-pointer invariant is not consistently maintained.
pushFrontleavesmiddlepointing to the head sentinel after the first insertion.pushMiddlealways inserts aftermiddle; for odd lengths, it must insert before it._popnever decrementssizeor updatesmiddle, leaving stale state and potentially a detached middle node.popBackpasses the last node to a helper that removes its successor, so it tries to remove the tail sentinel and dereferencesNone.
The two-deque approach avoids these pointer-update cases while preserving the same complexity.
# Ideas:
# - Use a doubly linked list
# [1, 3, 2]
# middle = n(3), 1
# [1, 3, 2, 4] # pushBack(4)
# middle = n(3), 1
# [1, 3, 2, 4, 5] # pushBack(5)
# middle = n(2), 2
# [3, 2, 4, 5] # popFront()
# middle = n(2), 1
# WRONG
class FrontMiddleBackQueue:
class _Node:
def __init__(self, val):
self.val = val
self.prev = None
self.next = None
def __init__(self):
self.head = self._Node(0)
self.tail = self._Node(0)
self.head.next = self.tail
self.tail.prev = self.head
self.middle = self.head
self.size = 0
def _push(self, val, prev):
node = self._Node(val)
node.next = prev.next
node.prev = prev
prev.next = prev.next.prev = node
return node
def pushFront(self, val: int) -> None:
self._push(val, self.head)
self.size += 1
if self.size % 2 == 0:
self.middle = self.middle.prev
def pushMiddle(self, val: int) -> None:
self.middle = self._push(val, self.middle)
self.size += 1
def pushBack(self, val: int) -> None:
self._push(val, self.tail.prev)
self.size += 1
if self.size % 2:
self.middle = self.middle.next
def _pop(self, prev):
if self.size == 0:
return -1
val = prev.next.val
prev.next = prev.next.next
prev.next.prev = prev
return val
def popFront(self) -> int:
return self._pop(self.head)
def popMiddle(self) -> int:
return self._pop(self.middle.prev)
def popBack(self) -> int:
return self._pop(self.tail.prev)
# WRONG
# updated after reading AI comments
# still left to update middle in _pop()
class FrontMiddleBackQueue:
class _Node:
def __init__(self, val):
self.val = val
self.prev = None
self.next = None
def __init__(self):
self.head = self._Node(0)
self.tail = self._Node(0)
self.head.next = self.tail
self.tail.prev = self.head
self.middle = self.head
self.size = 0
def _push(self, val, prev):
node = self._Node(val)
node.next = prev.next
node.prev = prev
prev.next = prev.next.prev = node
return node
def pushFront(self, val: int) -> None:
self._push(val, self.head)
self.size += 1
if self.size % 2 == 0:
self.middle = self.middle.prev
elif self.size == 1:
self.middle = self.head.next
def pushMiddle(self, val: int) -> None:
if self.size == 0:
self.pushFront(val)
return
if self.size % 2:
self.middle = self._push(val, self.middle.prev)
else:
self.middle = self._push(val, self.middle)
self.size += 1
def pushBack(self, val: int) -> None:
self._push(val, self.tail.prev)
self.size += 1
if self.size % 2:
self.middle = self.middle.next
def _pop(self, prev):
if self.size == 0:
return -1
val = prev.next.val
prev.next = prev.next.next
prev.next.prev = prev
return val
def popFront(self) -> int:
return self._pop(self.head)
def popMiddle(self) -> int:
return self._pop(self.middle.prev)
def popBack(self) -> int:
if self.size == 0:
return -1
return self._pop(self.tail.prev.prev)
# WORKS
# Doubly linked list fixed by AI
# Keep middle at index (n-1)//2 when nonempty, and at
# the head sentinel when empty. Update it before removing a node.
class FrontMiddleBackQueue:
class _Node:
def __init__(self, val):
self.val = val
self.prev = None
self.next = None
def __init__(self):
self.head = self._Node(0)
self.tail = self._Node(0)
self.head.next = self.tail
self.tail.prev = self.head
self.middle = self.head
self.size = 0
def _push(self, val, prev):
# Insert immediately after prev.
node = self._Node(val)
node.prev = prev
node.next = prev.next
prev.next.prev = node
prev.next = node
return node
def pushFront(self, val: int) -> None:
node = self._push(val, self.head)
self.size += 1
if self.size == 1:
self.middle = node
elif self.size % 2 == 0:
self.middle = self.middle.prev
def pushMiddle(self, val: int) -> None:
# Odd size: insert before middle. Even size: insert after it.
prev = self.middle.prev if self.size % 2 else self.middle
self.middle = self._push(val, prev)
self.size += 1
def pushBack(self, val: int) -> None:
node = self._push(val, self.tail.prev)
self.size += 1
if self.size == 1:
self.middle = node
elif self.size % 2:
self.middle = self.middle.next
def _pop(self, prev):
# Remove immediately after prev.
if self.size == 0:
return -1
node = prev.next
prev.next = node.next
node.next.prev = prev
self.size -= 1
if self.size == 0:
self.middle = self.head
return node.val
def popFront(self) -> int:
if self.size == 0:
return -1
# Removing the front shifts the middle right for even sizes.
if self.size % 2 == 0:
self.middle = self.middle.next
return self._pop(self.head)
def popMiddle(self) -> int:
if self.size == 0:
return -1
# Save the predecessor before moving the middle pointer.
prev = self.middle.prev
if self.size % 2 == 0:
self.middle = self.middle.next
else:
self.middle = self.middle.prev
return self._pop(prev)
def popBack(self) -> int:
if self.size == 0:
return -1
# Removing the back shifts the middle left for odd sizes.
if self.size % 2:
self.middle = self.middle.prev
# _pop removes the successor, so pass the last node's predecessor.
return self._pop(self.tail.prev.prev)