Problem editorial

Design Circular Deque

MediumDesign PatternsArrayLinked ListDesign

Editorial

Core insight

Design Circular Deque · Design Patterns

Core Insight for Design Circular Deque

The fundamental challenge in Design Circular Deque is managing the "wrap-around" behavior without physically moving data. The core insight is to decouple the logical index (where the next element goes) from the physical index (the actual memory address in the array).

We treat the linear array as a closed loop. If we are at the last index of the array and need to move forward, we jump back to index 0. If we are at index 0 and need to move backward, we jump to the last index.

This is achieved mathematically using the modulo operator (%).

Circular Increment: (index + 1) % capacity
Circular Decrement: (index - 1 + capacity) % capacity

By maintaining two pointers, front and rear, and a variable currentSize, we can perform all insertions and deletions by simply updating these integers. The front pointer tracks the head of the deque, while the rear pointer tracks the next available slot at the tail.

Visual Description: Imagine an array of size 5. Initially, front and rear are at 0. When we insertLast(A), A is placed at index 0, and rear moves to 1. If we fill the array up to index 4, the next insertLast places an element at index 0 (if it's free), effectively closing the loop. The front pointer moves "backward" (counter-clockwise) for insertFront and "forward" (clockwise) for deleteFront.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 641: Design Circular Deque Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes a fixed-size array combined with two pointers (front and rear) and modulo arithmetic to achieve $O(1)$ time complexity for all operations.

The Design Circular Deque problem asks us to implement a double-ended queue (deque) with a fixed maximum capacity $k$ . Unlike a standard dynamic queue that grows indefinitely, this structure must wrap around its allocated memory. We need to support adding and removing elements from both the front and the rear, as well as checking the status of the deque (empty or full), all while adhering to the fixed size constraint. This is a popular interview question that tests low-level understanding of array indexing and state management.

Brute Force Approach for Design Circular Deque

A naive approach to solving LeetCode 641 is to use a standard dynamic list (like std::vector in C++ or ArrayList in Java) and physically add or remove elements at the specified indices.

Pseudo-code:

text

class NaiveDeque:
    list data
    int capacity

    insertFront(val):
        if size == capacity: return false
        data.insert(0, val) // Shift all elements right
        return true

    insertLast(val):
        if size == capacity: return false
        data.append(val)
        return true

Time Complexity: The time complexity for insertLast is $O(1)$ , but insertFront and deleteFront are $O(k)$ because adding or removing elements at the beginning of an array requires shifting all subsequent elements in memory.

Why it fails: While this approach might pass correctness tests on small inputs, it fails the efficiency requirements expected in a system design context. A deque is defined by its ability to perform operations at both ends in constant time. Using $O(k)$ operations defeats the purpose of the data structure. Furthermore, this approach does not truly implement "circular" logic; it simply simulates a queue using a resizing array.

Algorithm Strategy: Design Patterns

We will use a fixed-size array of length $k$ to store elements. We maintain the following state variables:

buffer: An array of size $k$ .
front: An integer index pointing to the current front element.
rear: An integer index pointing to the next available position for insertion at the back.
count: An integer tracking the current number of elements.
capacity: The maximum size $k$ .

Constraints Enforcement:

Full Check: If count == capacity, insertion operations return false.
Empty Check: If count == 0, deletion or retrieval operations return false or -1.
Pointer Movement:
- insertFront: Move front backward cyclically, then place value.
- insertLast: Place value at rear, then move rear forward cyclically.
- deleteFront: Move front forward cyclically.
- deleteLast: Move rear backward cyclically.

Using a count variable simplifies the logic significantly compared to using only pointers, as it avoids the ambiguity where front == rear could mean either empty or full.

Execution Flow

Initialization:
- Create an array buffer of size $k$ .
- Set front = 0, rear = 0, count = 0.
insertLast(value):
- Check if isFull(). If yes, return false.
- Store value at buffer[rear].
- Update rear to (rear + 1) % k.
- Increment count.
- Return true.
insertFront(value):
- Check if isFull(). If yes, return false.
- Update front to (front - 1 + k) % k. (This moves front to the previous slot cyclically).
- Store value at buffer[front].
- Increment count.
- Return true.
deleteLast():
- Check if isEmpty(). If yes, return false.
- Update rear to (rear - 1 + k) % k. (This logically removes the element by moving the tail pointer back).
- Decrement count.
- Return true.
deleteFront():
- Check if isEmpty(). If yes, return false.
- Update front to (front + 1) % k.
- Decrement count.
- Return true.
getFront():
- If empty, return -1.
- Return buffer[front].
getRear():
- If empty, return -1.
- The actual last element is at (rear - 1 + k) % k, because rear points to the next open slot.
- Return buffer[(rear - 1 + k) % k].

Proof of Correctness

The correctness relies on the invariant that front always points to the first valid element and rear always points to the index immediately following the last valid element (circularly).

The modulo arithmetic ensures that indices always remain within the bounds $[0, k-1]$ .
The count variable accurately tracks the number of elements, preventing insert operations from overwriting unread data (overflow) and delete operations from reading garbage data (underflow).
By decoupling the circular logic from the physical array, we satisfy the interface requirements of a Deque with $O(1)$ complexity.

Pattern Reuse Notes

The Design pattern and circular buffer logic used here are fundamental to several other LeetCode problems:

LeetCode 146: LRU Cache - Requires designing a data structure with $O(1)$ access and updates, often using a combination of Hash Map and Doubly Linked List (conceptually similar to maintaining pointers).
LeetCode 155: Min Stack - Involves maintaining auxiliary state (metadata) alongside the main data to support $O(1)$ retrieval of the minimum element.
LeetCode 225: Implement Stack using Queues - Manipulating data structure constraints to mimic another structure's behavior.
LeetCode 232: Implement Queue using Stacks - Similar constraint manipulation, using two stacks to reverse order and simulate FIFO behavior.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 641

cpp

1class MyCircularDeque {
2private:
3    vector<int> buffer;
4    int front;
5    int rear;
6    int count;
7    int capacity;
8
9public:
10    MyCircularDeque(int k) {
11        buffer.resize(k);
12        capacity = k;
13        front = 0;
14        rear = 0;
15        count = 0;
16    }
17    
18    bool insertFront(int value) {
19        if (isFull()) return false;
20        // Move front back cyclically
21        front = (front - 1 + capacity) % capacity;
22        buffer[front] = value;
23        count++;
24        return true;
25    }
26    
27    bool insertLast(int value) {
28        if (isFull()) return false;
29        buffer[rear] = value;
30        // Move rear forward cyclically
31        rear = (rear + 1) % capacity;
32        count++;
33        return true;
34    }
35    
36    bool deleteFront() {
37        if (isEmpty()) return false;
38        // Move front forward cyclically
39        front = (front + 1) % capacity;
40        count--;
41        return true;
42    }
43    
44    bool deleteLast() {
45        if (isEmpty()) return false;
46        // Move rear back cyclically
47        rear = (rear - 1 + capacity) % capacity;
48        count--;
49        return true;
50    }
51    
52    int getFront() {
53        if (isEmpty()) return -1;
54        return buffer[front];
55    }
56    
57    int getRear() {
58        if (isEmpty()) return -1;
59        // Rear points to next slot, so actual data is at (rear - 1)
60        return buffer[(rear - 1 + capacity) % capacity];
61    }
62    
63    bool isEmpty() {
64        return count == 0;
65    }
66    
67    bool isFull() {
68        return count == capacity;
69    }
70};

Java Solution for LeetCode 641

java

1class MyCircularDeque {
2    private int[] buffer;
3    private int front;
4    private int rear;
5    private int count;
6    private int capacity;
7
8    public MyCircularDeque(int k) {
9        this.capacity = k;
10        this.buffer = new int[k];
11        this.front = 0;
12        this.rear = 0;
13        this.count = 0;
14    }
15    
16    public boolean insertFront(int value) {
17        if (isFull()) return false;
18        // Move front backward cyclically
19        front = (front - 1 + capacity) % capacity;
20        buffer[front] = value;
21        count++;
22        return true;
23    }
24    
25    public boolean insertLast(int value) {
26        if (isFull()) return false;
27        buffer[rear] = value;
28        // Move rear forward cyclically
29        rear = (rear + 1) % capacity;
30        count++;
31        return true;
32    }
33    
34    public boolean deleteFront() {
35        if (isEmpty()) return false;
36        // Move front forward cyclically to "delete"
37        front = (front + 1) % capacity;
38        count--;
39        return true;
40    }
41    
42    public boolean deleteLast() {
43        if (isEmpty()) return false;
44        // Move rear backward cyclically
45        rear = (rear - 1 + capacity) % capacity;
46        count--;
47        return true;
48    }
49    
50    public int getFront() {
51        if (isEmpty()) return -1;
52        return buffer[front];
53    }
54    
55    public int getRear() {
56        if (isEmpty()) return -1;
57        // Calculate index of the last valid element
58        return buffer[(rear - 1 + capacity) % capacity];
59    }
60    
61    public boolean isEmpty() {
62        return count == 0;
63    }
64    
65    public boolean isFull() {
66        return count == capacity;
67    }
68}

Python Solution for LeetCode 641

python

1class MyCircularDeque:
2
3    def __init__(self, k: int):
4        self.capacity = k
5        self.buffer = [0] * k
6        self.front = 0
7        self.rear = 0
8        self.count = 0
9
10    def insertFront(self, value: int) -> bool:
11        if self.isFull():
12            return False
13        # Python's % operator handles negative numbers correctly for wrapping
14        self.front = (self.front - 1) % self.capacity
15        self.buffer[self.front] = value
16        self.count += 1
17        return True
18
19    def insertLast(self, value: int) -> bool:
20        if self.isFull():
21            return False
22        self.buffer[self.rear] = value
23        self.rear = (self.rear + 1) % self.capacity
24        self.count += 1
25        return True
26
27    def deleteFront(self) -> bool:
28        if self.isEmpty():
29            return False
30        self.front = (self.front + 1) % self.capacity
31        self.count -= 1
32        return True
33
34    def deleteLast(self) -> bool:
35        if self.isEmpty():
36            return False
37        self.rear = (self.rear - 1) % self.capacity
38        self.count -= 1
39        return True
40
41    def getFront(self) -> int:
42        if self.isEmpty():
43            return -1
44        return self.buffer[self.front]
45
46    def getRear(self) -> int:
47        if self.isEmpty():
48            return -1
49        # Calculate index of the last valid element
50        return self.buffer[(self.rear - 1) % self.capacity]
51
52    def isEmpty(self) -> bool:
53        return self.count == 0
54
55    def isFull(self) -> bool:
56        return self.count == self.capacity

AI Coach Insight

For Design Circular Deque, focus on explaining why the structure works, not just naming Design Patterns.

Complexity Analysis

Time Complexity: $O(1)$ for all operations (insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull). All operations involve simple arithmetic calculations and array indexing, which take constant time.
Space Complexity: $O(k)$ where $k$ is the capacity of the deque. We pre-allocate an array of size $k$ to store the elements. The auxiliary space for pointers and state variables is $O(1)$ .

Related Patterns

Pattern: Design Patterns
Subpattern: Design (General/Specific)

This problem fits the Design pattern because it requires constructing a class with specific behavioral constraints (FIFO/LIFO properties and fixed capacity) rather than solving a single algorithmic computation. Specifically, it involves managing internal state pointers to simulate a logical structure (a ring) on top of a linear physical structure (an array).

Common Mistakes & FAQ

Why does my solution fail with negative results in Modulo?
- Mistake: In C++ and Java, (-1) % k evaluates to -1 (or similar), not k-1.
- Conceptual Gap: Understanding how the modulo operator handles negative operands in different languages.
- Consequence: This leads to IndexOutOfBoundsException or memory corruption. Always use (index - 1 + capacity) % capacity to ensure positive wrapping.
Why is my getRear returning the wrong value?
- Mistake: Returning buffer[rear] directly when rear points to the next available slot.
- Conceptual Gap: Pointer semantics. If rear indicates where the next item goes, the current last item is at the previous index.
- Consequence: Returns garbage data (usually 0 or an old overwritten value), causing correctness failure.
Why is distinguishing Full vs Empty difficult without a count variable?
- Mistake: Relying solely on front == rear to detect both empty and full states.
- Conceptual Gap: In a standard implementation, front == rear implies the queue is empty. However, if the queue fills up completely, rear wraps around and meets front again.
- Consequence: The logic cannot distinguish between a completely full buffer and a completely empty one. This forces the use of a "dummy" slot (allocating k+1 size) or a count variable.

Practise Design Circular Deque and the problems around it

Design Circular Deque is a Design Patterns problem, in the Design (General/Specific) subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Core insight

Design Circular Deque · Design Patterns

Core Insight for Design Circular Deque

This is achieved mathematically using the modulo operator (%).

Circular Increment: (index + 1) % capacity
Circular Decrement: (index - 1 + capacity) % capacity

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 641: Design Circular Deque Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes a fixed-size array combined with two pointers (front and rear) and modulo arithmetic to achieve $O(1)$ time complexity for all operations.

Brute Force Approach for Design Circular Deque

A naive approach to solving LeetCode 641 is to use a standard dynamic list (like std::vector in C++ or ArrayList in Java) and physically add or remove elements at the specified indices.

Pseudo-code:

text

class NaiveDeque:
    list data
    int capacity

    insertFront(val):
        if size == capacity: return false
        data.insert(0, val) // Shift all elements right
        return true

    insertLast(val):
        if size == capacity: return false
        data.append(val)
        return true

Algorithm Strategy: Design Patterns

We will use a fixed-size array of length $k$ to store elements. We maintain the following state variables:

buffer: An array of size $k$ .
front: An integer index pointing to the current front element.
rear: An integer index pointing to the next available position for insertion at the back.
count: An integer tracking the current number of elements.
capacity: The maximum size $k$ .

Constraints Enforcement:

Full Check: If count == capacity, insertion operations return false.
Empty Check: If count == 0, deletion or retrieval operations return false or -1.
Pointer Movement:
- insertFront: Move front backward cyclically, then place value.
- insertLast: Place value at rear, then move rear forward cyclically.
- deleteFront: Move front forward cyclically.
- deleteLast: Move rear backward cyclically.

Using a count variable simplifies the logic significantly compared to using only pointers, as it avoids the ambiguity where front == rear could mean either empty or full.

Execution Flow

Initialization:
- Create an array buffer of size $k$ .
- Set front = 0, rear = 0, count = 0.
insertLast(value):
- Check if isFull(). If yes, return false.
- Store value at buffer[rear].
- Update rear to (rear + 1) % k.
- Increment count.
- Return true.
insertFront(value):
- Check if isFull(). If yes, return false.
- Update front to (front - 1 + k) % k. (This moves front to the previous slot cyclically).
- Store value at buffer[front].
- Increment count.
- Return true.
deleteLast():
- Check if isEmpty(). If yes, return false.
- Update rear to (rear - 1 + k) % k. (This logically removes the element by moving the tail pointer back).
- Decrement count.
- Return true.
deleteFront():
- Check if isEmpty(). If yes, return false.
- Update front to (front + 1) % k.
- Decrement count.
- Return true.
getFront():
- If empty, return -1.
- Return buffer[front].
getRear():
- If empty, return -1.
- The actual last element is at (rear - 1 + k) % k, because rear points to the next open slot.
- Return buffer[(rear - 1 + k) % k].

Proof of Correctness

The correctness relies on the invariant that front always points to the first valid element and rear always points to the index immediately following the last valid element (circularly).

The modulo arithmetic ensures that indices always remain within the bounds $[0, k-1]$ .
The count variable accurately tracks the number of elements, preventing insert operations from overwriting unread data (overflow) and delete operations from reading garbage data (underflow).
By decoupling the circular logic from the physical array, we satisfy the interface requirements of a Deque with $O(1)$ complexity.

Pattern Reuse Notes

The Design pattern and circular buffer logic used here are fundamental to several other LeetCode problems:

LeetCode 146: LRU Cache - Requires designing a data structure with $O(1)$ access and updates, often using a combination of Hash Map and Doubly Linked List (conceptually similar to maintaining pointers).
LeetCode 155: Min Stack - Involves maintaining auxiliary state (metadata) alongside the main data to support $O(1)$ retrieval of the minimum element.
LeetCode 225: Implement Stack using Queues - Manipulating data structure constraints to mimic another structure's behavior.
LeetCode 232: Implement Queue using Stacks - Similar constraint manipulation, using two stacks to reverse order and simulate FIFO behavior.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 641

cpp

1class MyCircularDeque {
2private:
3    vector<int> buffer;
4    int front;
5    int rear;
6    int count;
7    int capacity;
8
9public:
10    MyCircularDeque(int k) {
11        buffer.resize(k);
12        capacity = k;
13        front = 0;
14        rear = 0;
15        count = 0;
16    }
17    
18    bool insertFront(int value) {
19        if (isFull()) return false;
20        // Move front back cyclically
21        front = (front - 1 + capacity) % capacity;
22        buffer[front] = value;
23        count++;
24        return true;
25    }
26    
27    bool insertLast(int value) {
28        if (isFull()) return false;
29        buffer[rear] = value;
30        // Move rear forward cyclically
31        rear = (rear + 1) % capacity;
32        count++;
33        return true;
34    }
35    
36    bool deleteFront() {
37        if (isEmpty()) return false;
38        // Move front forward cyclically
39        front = (front + 1) % capacity;
40        count--;
41        return true;
42    }
43    
44    bool deleteLast() {
45        if (isEmpty()) return false;
46        // Move rear back cyclically
47        rear = (rear - 1 + capacity) % capacity;
48        count--;
49        return true;
50    }
51    
52    int getFront() {
53        if (isEmpty()) return -1;
54        return buffer[front];
55    }
56    
57    int getRear() {
58        if (isEmpty()) return -1;
59        // Rear points to next slot, so actual data is at (rear - 1)
60        return buffer[(rear - 1 + capacity) % capacity];
61    }
62    
63    bool isEmpty() {
64        return count == 0;
65    }
66    
67    bool isFull() {
68        return count == capacity;
69    }
70};

Java Solution for LeetCode 641

java

1class MyCircularDeque {
2    private int[] buffer;
3    private int front;
4    private int rear;
5    private int count;
6    private int capacity;
7
8    public MyCircularDeque(int k) {
9        this.capacity = k;
10        this.buffer = new int[k];
11        this.front = 0;
12        this.rear = 0;
13        this.count = 0;
14    }
15    
16    public boolean insertFront(int value) {
17        if (isFull()) return false;
18        // Move front backward cyclically
19        front = (front - 1 + capacity) % capacity;
20        buffer[front] = value;
21        count++;
22        return true;
23    }
24    
25    public boolean insertLast(int value) {
26        if (isFull()) return false;
27        buffer[rear] = value;
28        // Move rear forward cyclically
29        rear = (rear + 1) % capacity;
30        count++;
31        return true;
32    }
33    
34    public boolean deleteFront() {
35        if (isEmpty()) return false;
36        // Move front forward cyclically to "delete"
37        front = (front + 1) % capacity;
38        count--;
39        return true;
40    }
41    
42    public boolean deleteLast() {
43        if (isEmpty()) return false;
44        // Move rear backward cyclically
45        rear = (rear - 1 + capacity) % capacity;
46        count--;
47        return true;
48    }
49    
50    public int getFront() {
51        if (isEmpty()) return -1;
52        return buffer[front];
53    }
54    
55    public int getRear() {
56        if (isEmpty()) return -1;
57        // Calculate index of the last valid element
58        return buffer[(rear - 1 + capacity) % capacity];
59    }
60    
61    public boolean isEmpty() {
62        return count == 0;
63    }
64    
65    public boolean isFull() {
66        return count == capacity;
67    }
68}

Python Solution for LeetCode 641

python

1class MyCircularDeque:
2
3    def __init__(self, k: int):
4        self.capacity = k
5        self.buffer = [0] * k
6        self.front = 0
7        self.rear = 0
8        self.count = 0
9
10    def insertFront(self, value: int) -> bool:
11        if self.isFull():
12            return False
13        # Python's % operator handles negative numbers correctly for wrapping
14        self.front = (self.front - 1) % self.capacity
15        self.buffer[self.front] = value
16        self.count += 1
17        return True
18
19    def insertLast(self, value: int) -> bool:
20        if self.isFull():
21            return False
22        self.buffer[self.rear] = value
23        self.rear = (self.rear + 1) % self.capacity
24        self.count += 1
25        return True
26
27    def deleteFront(self) -> bool:
28        if self.isEmpty():
29            return False
30        self.front = (self.front + 1) % self.capacity
31        self.count -= 1
32        return True
33
34    def deleteLast(self) -> bool:
35        if self.isEmpty():
36            return False
37        self.rear = (self.rear - 1) % self.capacity
38        self.count -= 1
39        return True
40
41    def getFront(self) -> int:
42        if self.isEmpty():
43            return -1
44        return self.buffer[self.front]
45
46    def getRear(self) -> int:
47        if self.isEmpty():
48            return -1
49        # Calculate index of the last valid element
50        return self.buffer[(self.rear - 1) % self.capacity]
51
52    def isEmpty(self) -> bool:
53        return self.count == 0
54
55    def isFull(self) -> bool:
56        return self.count == self.capacity

Design Circular Deque

Core insight

Core Insight for Design Circular Deque

Full breakdown

LeetCode 641: Design Circular Deque Solution & Explanation

Problem Overview

Brute Force Approach for Design Circular Deque

Algorithm Strategy: Design Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 641

Java Solution for LeetCode 641

Python Solution for LeetCode 641

Practise Design Circular Deque and the problems around it

Related problems

Design Circular Deque

Core insight

Core Insight for Design Circular Deque

Full breakdown

LeetCode 641: Design Circular Deque Solution & Explanation

Problem Overview

Brute Force Approach for Design Circular Deque

Algorithm Strategy: Design Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 641

Java Solution for LeetCode 641

Python Solution for LeetCode 641

Practise Design Circular Deque and the problems around it

Related problems