Design Circular Deque — Array-Based Implementation (LeetCode 641)

A deque (double-ended queue) supports insertion and deletion at both ends. A circular deque uses a fixed-size array with wrap-around indexing, so no space is wasted. LeetCode 641 asks you to design one from scratch.

The Interface

You need to implement these methods:

Method	Description	Time
MyCircularDeque(k)	Create deque of capacity k	O(k)
insertFront(val)	Add to front	O(1)
insertLast(val)	Add to rear	O(1)
deleteFront()	Remove from front	O(1)
deleteLast()	Remove from rear	O(1)
getFront()	Peek front	O(1)
getRear()	Peek rear	O(1)
isEmpty()	Check empty	O(1)
isFull()	Check full	O(1)

The Circular Array Idea

Use an array of size k, a front pointer, a rear pointer, and a size counter.

• front points to the first element
• rear points to the last element
• Wrap-around with modular arithmetic: (index + 1) % k or (index - 1 + k) % k

Using a size counter is simpler than the “waste one slot” approach because you do not lose a slot and the empty/full checks are trivial.

Python Implementation

class MyCircularDeque:
    """
    Array-based circular deque.
    Time: O(1) for all operations.
    Space: O(k) for the internal array.
    """

    def __init__(self, k: int):
        self.arr = [0] * k
        self.capacity = k
        self.size = 0
        self.front = 0
        self.rear = k - 1  # rear starts before front (empty state)

    def insertFront(self, value: int) -> bool:
        if self.isFull():
            return False
        # Move front backward (wrap around)
        self.front = (self.front - 1 + self.capacity) % self.capacity
        self.arr[self.front] = value
        self.size += 1
        return True

    def insertLast(self, value: int) -> bool:
        if self.isFull():
            return False
        # Move rear forward (wrap around)
        self.rear = (self.rear + 1) % self.capacity
        self.arr[self.rear] = value
        self.size += 1
        return True

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

    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False
        # Move rear backward
        self.rear = (self.rear - 1 + self.capacity) % self.capacity
        self.size -= 1
        return True

    def getFront(self) -> int:
        if self.isEmpty():
            return -1
        return self.arr[self.front]

    def getRear(self) -> int:
        if self.isEmpty():
            return -1
        return self.arr[self.rear]

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

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

Step-by-Step Trace

Create a deque with capacity k=4 and perform a series of operations:

MyCircularDeque(4):
  arr = [0, 0, 0, 0], front=0, rear=3, size=0

insertLast(1):  rear=(3+1)%4=0, arr[0]=1, size=1
  arr = [1, 0, 0, 0], front=0, rear=0

insertLast(2):  rear=(0+1)%4=1, arr[1]=2, size=2
  arr = [1, 2, 0, 0], front=0, rear=1

insertFront(5): front=(0-1+4)%4=3, arr[3]=5, size=3
  arr = [1, 2, 0, 5], front=3, rear=1

insertFront(8): front=(3-1+4)%4=2, arr[2]=8, size=4
  arr = [1, 2, 8, 5], front=2, rear=1

isFull(): size==4==capacity → True

insertLast(9): full → return False

getFront(): arr[2] = 8
getRear():  arr[1] = 2

deleteFront(): front=(2+1)%4=3, size=3
  arr = [1, 2, 8, 5], front=3, rear=1
  (arr[2]=8 is "logically deleted" — ignored)

getFront(): arr[3] = 5

deleteLast(): rear=(1-1+4)%4=0, size=2
  arr = [1, 2, 8, 5], front=3, rear=0

getRear(): arr[0] = 1

Understanding Wrap-Around

The key formula is modular arithmetic:

# Move forward (insertLast, deleteFront):
new_index = (index + 1) % capacity

# Move backward (insertFront, deleteLast):
new_index = (index - 1 + capacity) % capacity

Adding capacity before the modulo prevents negative indices. For example, with capacity=4:

• (0 - 1 + 4) % 4 = 3 — wraps from slot 0 back to slot 3

Why Use a Size Counter?

An alternative design uses the convention “rear points to the next empty slot” and wastes one array slot to distinguish empty from full. Our size counter approach has these advantages:

Approach	Pros	Cons
Size counter	Full capacity, easy empty/full	Extra int
Waste one slot	No extra variable	Loses one slot

For a capacity-k deque, the wasted-slot approach allocates k+1 slots. The size-counter approach allocates exactly k. Either works for interviews.

Common Mistakes

1. Forgetting + capacity in backward moves — (index - 1) % capacity can give negative values in some languages (Python handles it, but C++/Java do not)
2. Off-by-one on rear initialization — if front starts at 0 and rear starts at 0, inserting the first element can overwrite front
3. Not checking full/empty before insert/delete
4. Confusing front and rear directions — front moves backward on insertFront, forward on deleteFront

Edge Cases

1. Capacity 1 — single-element deque, front and rear always the same index
2. Insert when full — must return False
3. Delete when empty — must return False
4. Alternating front/rear inserts — tests wrap-around thoroughly
5. Fill, empty, refill — verifies the circular reuse works

Complexity Analysis

Operation	Time	Space
All operations	O(1)	-
Total space	-	O(k)

When to Use This Pattern

Use a circular deque when:

• You need O(1) insertion/deletion at both ends
• The maximum size is known in advance
• You want a fixed-memory data structure (no dynamic allocation)
• Sliding window problems that need to remove from both ends

Related Problems

Problem	Difficulty	Key Idea
LeetCode 641 — Design Circular Deque	Medium	This problem
LeetCode 622 — Design Circular Queue	Medium	Simpler one-ended version
LeetCode 239 — Sliding Window Maximum	Hard	Uses deque for O(n) solution
LeetCode 862 — Shortest Subarray with Sum at Least K	Hard	Monotonic deque

Key Takeaway

A circular deque is an array with two pointers that move in opposite directions. Modular arithmetic handles wrap-around. With a size counter, isEmpty and isFull are trivial. This is a foundational data structure that appears in sliding window problems and OS schedulers.