LeetCode 641: Design Circular Deque

Problem Restatement

We need to design a circular double-ended queue.

A deque supports insertion and deletion from both ends:

The deque has a fixed maximum capacity k.

If we try to insert into a full deque, the operation should return False.

If we try to delete from an empty deque, the operation should return False.

If we try to read from an empty deque, the operation should return -1.

Input and Output

Class shape:

class MyCircularDeque:

    def __init__(self, k: int):
        ...

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

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

    def deleteFront(self) -> bool:
        ...

    def deleteLast(self) -> bool:
        ...

    def getFront(self) -> int:
        ...

    def getRear(self) -> int:
        ...

    def isEmpty(self) -> bool:
        ...

    def isFull(self) -> bool:
        ...

The official operations require O(1) behavior for insertion, deletion, front access, rear access, and empty/full checks.

Example

Operations:

deque = MyCircularDeque(3)

deque.insertLast(1)    # True
deque.insertLast(2)    # True
deque.insertFront(3)   # True
deque.insertFront(4)   # False
deque.getRear()        # 2
deque.isFull()         # True
deque.deleteLast()     # True
deque.insertFront(4)   # True
deque.getFront()       # 4

After inserting 1, 2, and 3, the deque has capacity 3, so it is full.

That is why:

deque.insertFront(4)

returns:

False

After deleting from the rear, there is space again, so inserting 4 at the front succeeds.

First Thought: Use a Python List

A simple implementation could use a list.

self.data.insert(0, value)
self.data.append(value)
self.data.pop(0)
self.data.pop()

This works logically, but insert(0, value) and pop(0) are O(n) because all later elements must shift.

We need all operations to be constant time.

Key Insight

Use a fixed-size array as a circular buffer.

The array has length k.

Instead of physically shifting elements, we keep:

The rear index can be computed from front and size:

rear = (front + size - 1) % capacity

The modulo operator makes the index wrap around.

For example, if capacity = 3, then after index 2, the next index is:

(2 + 1) % 3 = 0

That is the circular part.

Index Rules

When inserting at the front, the new front is one step before the old front:

front = (front - 1) % capacity

When deleting from the front, the new front is one step after the old front:

front = (front + 1) % capacity

When inserting at the rear, the rear index is the first empty slot after the current last element:

rear = (front + size) % capacity

When reading the rear, the rear index is:

rear = (front + size - 1) % capacity

These formulas avoid shifting elements.

Algorithm

Initialize:

data = [0] * k
front = 0
size = 0
capacity = k

For insertFront(value):

1. If full, return False.
2. Move front backward with modulo.
3. Write value at front.
4. Increase size.
5. Return True.

For insertLast(value):

1. If full, return False.
2. Compute the rear insertion index.
3. Write value.
4. Increase size.
5. Return True.

For deleteFront():

1. If empty, return False.
2. Move front forward.
3. Decrease size.
4. Return True.

For deleteLast():

1. If empty, return False.
2. Decrease size.
3. Return True.

For getFront():

1. If empty, return -1.
2. Return data[front].

For getRear():

1. If empty, return -1.
2. Compute rear index.
3. Return data[rear].

Implementation

class MyCircularDeque:

    def __init__(self, k: int):
        self.data = [0] * k
        self.capacity = k
        self.front = 0
        self.size = 0

    def insertFront(self, value: int) -> bool:
        if self.isFull():
            return False

        self.front = (self.front - 1) % self.capacity
        self.data[self.front] = value
        self.size += 1

        return True

    def insertLast(self, value: int) -> bool:
        if self.isFull():
            return False

        index = (self.front + self.size) % self.capacity
        self.data[index] = value
        self.size += 1

        return True

    def deleteFront(self) -> bool:
        if self.isEmpty():
            return False

        self.front = (self.front + 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:
        if self.isEmpty():
            return -1

        return self.data[self.front]

    def getRear(self) -> int:
        if self.isEmpty():
            return -1

        index = (self.front + self.size - 1) % self.capacity
        return self.data[index]

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

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

Code Explanation

The array is fixed-size:

self.data = [0] * k

We do not resize it.

The size variable distinguishes empty from full:

self.size = 0

Without size, front == rear could mean either empty or full, which complicates the design.

Insertion at the front moves front backward:

self.front = (self.front - 1) % self.capacity

In Python, modulo handles negative values cleanly:

-1 % 3 == 2

So if front is 0, moving backward wraps to the last array index.

Insertion at the rear writes after the current last element:

index = (self.front + self.size) % self.capacity

Then size increases.

Deleting from the rear only needs:

self.size -= 1

The rear index is computed from front and size, so no separate rear pointer needs to be updated.

Correctness

The implementation maintains this invariant:

The deque elements occupy size positions starting at front, wrapping around the array if needed.

For insertFront, the algorithm moves front one position backward and stores the new value there. This places the value before all existing elements, so it becomes the new front.

For insertLast, the algorithm writes to (front + size) % capacity, which is exactly the first empty slot after the current rear. This places the value after all existing elements, so it becomes the new rear.

For deleteFront, the algorithm moves front one position forward and decreases size. This removes the old front from the logical deque.

For deleteLast, the algorithm decreases size. Since the rear index is derived from front + size - 1, reducing size removes the old rear from the logical deque.

getFront returns the element at front, which is the first logical element. getRear computes the last logical index and returns that value.

The isEmpty and isFull methods directly compare size with 0 and capacity, so they correctly detect underflow and overflow conditions.

Therefore, every operation satisfies the required deque behavior.

Complexity

Let k be the capacity.

Alternative: Track Both Front and Rear

Another valid design stores both front and rear pointers.

In that version, rear points to the current rear element.

This can make getRear simpler, but every insert and delete must update both pointer state and size carefully.

The front + size design keeps less state, which reduces the chance of pointer drift.

Testing

def run_tests():
    dq = MyCircularDeque(3)

    assert dq.insertLast(1) is True
    assert dq.insertLast(2) is True
    assert dq.insertFront(3) is True
    assert dq.insertFront(4) is False
    assert dq.getRear() == 2
    assert dq.isFull() is True
    assert dq.deleteLast() is True
    assert dq.insertFront(4) is True
    assert dq.getFront() == 4

    dq = MyCircularDeque(1)
    assert dq.isEmpty() is True
    assert dq.getFront() == -1
    assert dq.getRear() == -1
    assert dq.insertFront(10) is True
    assert dq.isFull() is True
    assert dq.insertLast(20) is False
    assert dq.getFront() == 10
    assert dq.getRear() == 10
    assert dq.deleteFront() is True
    assert dq.deleteLast() is False

    dq = MyCircularDeque(2)
    assert dq.insertLast(1) is True
    assert dq.insertLast(2) is True
    assert dq.deleteFront() is True
    assert dq.insertLast(3) is True
    assert dq.getFront() == 2
    assert dq.getRear() == 3

    print("all tests passed")

run_tests()

Test meaning: