Domain 2MediumCORE

Design Circular Deque

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.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Design#Queue

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:

  1. Fixed Capacity: We cannot grow beyond size k. Operations must return false if full or empty as appropriate.
  2. Circular Behavior: When the array fills up, we shouldn’t shift elements (which is O(N)). Instead, indices should wrap around using modulo arithmetic.
  3. Return Values: Insert/Delete operations return a boolean indicating success. Get operations return -1 if empty.
  4. 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

  1. Data Structure: Initialize a list/array of size k.
  2. 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).
  3. Logic:
    • Insert Front: Decrement head. If head becomes -1, wrap to k-1. Check if count == k before inserting.
    • Insert Last: Increment tail. If tail reaches k, wrap to 0. Check if count == k.
    • Delete Front: Increment head. Wrap if needed. Decrement count.
    • Delete Last: Decrement tail. Wrap if needed. Decrement count.
    • Get Operations: Access values directly using head or (tail - 1) % k. Return -1 if count == 0.
  4. Modulo Arithmetic: Python’s % operator handles negative numbers correctly for wrapping (e.g., -1 % 3 is 2), 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/getRear return -1. Logic prevents accessing invalid indices when count is 0.
  • Full Deque: isFull() returns true; insertFront/insertLast return false without modifying state.
  • Wrap-Around Indices: Modulo arithmetic (index + k) % k ensures head and tail stay 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; head and tail will be adjacent or identical depending on state.
  • Negative Returns: Explicitly handled in getFront and getRear by checking isEmpty() first.