641. Design Circular Deque
Model: qwen3.5:9b
Topics: Design,Queue
FAANG asked: 1
Acceptance rate: 56.5%
Problem Breakdown
We need to implement a fixed-size circular double-ended queue (deque). The core requirement is that we can add/remove elements from both the front and rear in constant time, while respecting a maximum capacity k.
Key constraints:
- Fixed Capacity: We cannot grow beyond size
k. Operations must returnfalseif full or empty as appropriate. - Circular Behavior: When the array fills up, we shouldn’t shift elements (which is O(N)). Instead, indices should wrap around using modulo arithmetic.
- Return Values: Insert/Delete operations return a boolean indicating success. Get operations return -1 if empty.
- No Built-ins: We must implement the underlying storage logic ourselves (no
collections.deque).
Intuition
A naive implementation would use a standard Python list and insert/delete at indices 0 or -1. However, inserting at index 0 in a list requires shifting all subsequent elements to the right, resulting in O(N) time complexity per operation. This violates the requirement for efficient deque operations.
The key insight is to treat the underlying storage as a circular buffer. Instead of shifting data, we maintain two pointers: head (pointing to the first element) and tail (pointing to the next available slot). When an operation causes an index to go out of bounds (e.g., head becomes -1 or tail reaches k), we wrap the index back to 0 using modulo arithmetic. This allows us to reuse empty slots at the beginning of the array once elements are deleted from the front, keeping operations O(1).
Approach
- Data Structure: Initialize a list/array of size
k. - Pointers:
head: Index of the first element in the deque.tail: Index of the next empty slot after the last element.count: Tracks the number of elements currently in the deque (simplifies full/empty checks).
- Logic:
- Insert Front: Decrement
head. Ifheadbecomes -1, wrap tok-1. Check ifcount == kbefore inserting. - Insert Last: Increment
tail. Iftailreachesk, wrap to 0. Check ifcount == k. - Delete Front: Increment
head. Wrap if needed. Decrementcount. - Delete Last: Decrement
tail. Wrap if needed. Decrementcount. - Get Operations: Access values directly using
heador(tail - 1) % k. Return -1 ifcount == 0.
- Insert Front: Decrement
- Modulo Arithmetic: Python’s
%operator handles negative numbers correctly for wrapping (e.g.,-1 % 3is2), which simplifies the wrap-around logic.
Complexity Analysis
- Time Complexity: O(1) for all operations (
insert,delete,get). This is because we only update indices and do not shift data. - Space Complexity: O(k) to store the elements in the underlying array of fixed size
k.
Solution
class MyCircularDeque:
def __init__(self, k: int):
self.capacity = k
self.arr = [0] * k
self.head = 0
self.tail = 0
self.count = 0
def insertFront(self, value: int) -> bool:
if self.isFull():
return False
# Move head back (wrap around)
self.head = (self.head - 1 + self.capacity) % self.capacity
self.arr[self.head] = value
self.count += 1
return True
def insertLast(self, value: int) -> bool:
if self.isFull():
return False
# Move tail forward (wrap around)
self.tail = (self.tail + 1) % self.capacity
self.arr[self.tail] = value
self.count += 1
return True
def deleteFront(self) -> bool:
if self.isEmpty():
return False
self.head = (self.head + 1) % self.capacity
self.count -= 1
return True
def deleteLast(self) -> bool:
if self.isEmpty():
return False
self.tail = (self.tail - 1 + self.capacity) % self.capacity
self.count -= 1
return True
def getFront(self) -> int:
if self.isEmpty():
return -1
return self.arr[self.head]
def getRear(self) -> int:
if self.isEmpty():
return -1
# tail points to next empty, so rear is at tail - 1
return self.arr[(self.tail - 1 + self.capacity) % self.capacity]
def isEmpty(self) -> bool:
return self.count == 0
def isFull(self) -> bool:
return self.count == self.capacity
Edge Cases Handled
- Empty Deque:
isEmpty()returns true;getFront/getRearreturn -1. Logic prevents accessing invalid indices when count is 0. - Full Deque:
isFull()returns true;insertFront/insertLastreturn false without modifying state. - Wrap-Around Indices: Modulo arithmetic
(index + k) % kensuresheadandtailstay within[0, k-1]even when crossing the boundary (e.g., moving from index 0 to -1). - Single Element Operations: Logic holds for deque size 1;
headandtailwill be adjacent or identical depending on state. - Negative Returns: Explicitly handled in
getFrontandgetRearby checkingisEmpty()first.