Skip to content

641. Design Circular Deque

On LeetCode ->

Problem

Implement a fixed-capacity deque with insertion, deletion, and inspection at both ends.

  • Insertions return False when full; deletions return False when empty.
  • Successful insertions and deletions return True.
  • Reading either end returns -1 when empty.
  • Provide isEmpty() and isFull().
Capacity: 2
Operation          Result   State (front → rear)
insertLast(7)      True     [7]
insertFront(3)     True     [3, 7]
insertLast(9)      False    [3, 7]
deleteLast()       True     [3]
getFront()         3        [3]

class MyCircularDeque:
    def __init__(self, k: int):
        pass

    def insertFront(self, value: int) -> bool:
        pass

    def insertLast(self, value: int) -> bool:
        pass

    def deleteFront(self) -> bool:
        pass

    def deleteLast(self) -> bool:
        pass

    def getFront(self) -> int:
        pass

    def getRear(self) -> int:
        pass

    def isEmpty(self) -> bool:
        pass

    def isFull(self) -> bool:
        pass

Key trick

Use a fixed array, a front index, and a size; logical position \(i\) maps to array index \((head + i) \bmod k\).

Trap

An index alone cannot distinguish empty from full; track size, check boundaries before modifying state, and avoid shifting array elements.

Why is it interesting?

It turns a seemingly dynamic structure into constant-time operations over fixed storage using a small, precise invariant.

Python solution

class MyCircularDeque:
    def __init__(self, k: int):
        self.capacity = k
        self.values = [0] * k
        self.head = 0
        self.size = 0

    def insertFront(self, value: int) -> bool:
        if self.isFull():
            return False
        self.head = (self.head - 1) % self.capacity
        self.values[self.head] = value
        self.size += 1
        return True

    def insertLast(self, value: int) -> bool:
        if self.isFull():
            return False
        # The next free slot follows the logical rear.
        idx = (self.head + self.size) % self.capacity
        self.values[idx] = value
        self.size += 1
        return True

    def deleteFront(self) -> bool:
        if self.isEmpty():
            return False
        self.head = (self.head + 1) % self.capacity
        self.size -= 1
        return True

    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False
        # Removed slots need not be cleared: size defines valid entries.
        self.size -= 1
        return True

    def getFront(self) -> int:
        return -1 if self.isEmpty() else self.values[self.head]

    def getRear(self) -> int:
        if self.isEmpty():
            return -1
        idx = (self.head + self.size - 1) % self.capacity
        return self.values[idx]

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == self.capacity

Time: \(O(k)\) initialization; \(O(1)\) per operation. Space: \(O(k)\).

Comment on my solution

Your implementation is correct and interview-ready, with optimal operation complexity. Computing the rear index before checking emptiness is harmless because capacity is positive, but checking first makes the intent clearer; deleted slots do not need clearing.

class MyCircularDeque:
    def __init__(self, k: int):
        self.capacity = k
        self.values = [0] * k
        self.head = 0
        self.size = 0


    def insertFront(self, value: int) -> bool:
        if self.isFull():
            return False
        self.head = (self.head - 1) % self.capacity
        self.values[self.head] = value
        self.size += 1
        return True

    def insertLast(self, value: int) -> bool:
        if self.isFull():
            return False
        self.values[(self.head + self.size) % self.capacity] = value
        self.size += 1
        return True

    def deleteFront(self) -> bool:
        if self.isEmpty():
            return False
        self.head = (self.head + 1) % self.capacity
        self.size -= 1
        return True

    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False
        self.size -= 1
        return True

    def getFront(self) -> int:
        return -1 if self.isEmpty() else self.values[self.head]

    def getRear(self) -> int:
        idx = (self.head + self.size - 1) % self.capacity
        return -1 if self.isEmpty() else self.values[idx]

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == self.capacity