641. Design Circular Deque - Solution

Q: Is Design Circular Deque easy or hard?

Design Circular Deque is classified as a Medium problem. The difficulty comes from correctly handling edge cases such as wrap-around indexing, full vs empty states, and maintaining constant-time operations for all deque methods.

Q: Design Circular Deque Python/Java solution

Python and Java solutions typically implement the circular array approach with a fixed array, two pointers (front and rear), and a size counter. Each operation updates indices using modulo arithmetic so insertions and deletions remain O(1).

Q: How to solve Design Circular Deque in O(1)?

Use a fixed-size circular array and track two indices representing the front and rear of the deque. Update indices using modular arithmetic when inserting or deleting elements so they wrap around the array. This avoids shifting elements and guarantees O(1) time per operation.

Q: What is the best approach for Design Circular Deque?

The circular array approach is the most efficient and commonly expected solution. It uses modular arithmetic to wrap indices around the array, allowing insertions and deletions from both ends in O(1) time with O(k) space. This approach avoids node allocations and keeps memory contiguous.

Q: Is Design Circular Deque asked at Google/Amazon/Meta?

Deque design and circular buffer problems frequently appear in interviews at companies like Amazon, Google, and Meta. They test understanding of data structure design, pointer/index manipulation, and constant-time operations.

Q: What data structure is used in Design Circular Deque?

The problem can be implemented using either a circular array or a doubly linked list. A circular array uses index arithmetic to reuse array space, while a doubly linked list uses nodes with prev and next pointers to support efficient operations at both ends.

Q: What is the time complexity of Design Circular Deque?

All required operations—insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, and isFull—run in O(1) time. Both circular array and doubly linked list implementations achieve constant-time operations because they modify only indices or pointers.

The problem

Design your implementation of the circular double-ended queue (deque).

Implement the MyCircularDeque class:

MyCircularDeque(int k) Initializes the deque with a maximum size of k.
boolean insertFront() Adds an item at the front of Deque. Returns true if the operation is successful, or false otherwise.
boolean insertLast() Adds an item at the rear of Deque. Returns true if the operation is successful, or false otherwise.
boolean deleteFront() Deletes an item from the front of Deque. Returns true if the operation is successful, or false otherwise.
boolean deleteLast() Deletes an item from the rear of Deque. Returns true if the operation is successful, or false otherwise.
int getFront() Returns the front item from the Deque. Returns -1 if the deque is empty.
int getRear() Returns the last item from Deque. Returns -1 if the deque is empty.
boolean isEmpty() Returns true if the deque is empty, or false otherwise.
boolean isFull() Returns true if the deque is full, or false otherwise.

Example 1:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

Explanation
MyCircularDeque myCircularDeque = new MyCircularDeque(3);
myCircularDeque.insertLast(1);  // return True
myCircularDeque.insertLast(2);  // return True
myCircularDeque.insertFront(3); // return True
myCircularDeque.insertFront(4); // return False, the queue is full.
myCircularDeque.getRear();      // return 2
myCircularDeque.isFull();       // return True
myCircularDeque.deleteLast();   // return True
myCircularDeque.insertFront(4); // return True
myCircularDeque.getFront();     // return 4

Constraints:

1 <= k <= 1000
0 <= value <= 1000
At most 2000 calls will be made to insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull.

Approach overview

Problem Overview: Design a double-ended queue (deque) with a fixed capacity that behaves like a circular buffer. You must support operations such as insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, and isFull in constant time.

Approach 1: Circular Array (O(1) time, O(k) space)

This approach stores elements in a fixed-size array and treats it as circular using modular arithmetic. Maintain two pointers: front and rear. When inserting at the front, decrement the front index using (front - 1 + capacity) % capacity. When inserting at the rear, increment rear using (rear + 1) % capacity. Deletions move the pointers in the opposite direction. The key insight is that wrap‑around indexing lets the array reuse freed positions instead of shifting elements. A counter or size variable helps detect isFull and isEmpty. All operations run in O(1) time with O(k) space, where k is the deque capacity. This approach leverages simple memory layout and cache-friendly access patterns using an array.

Approach 2: Doubly Linked List (O(1) time, O(k) space)

A linked list implementation models the deque with nodes that store prev and next pointers. Maintain two references: head for the front and tail for the rear. Insertions at either end create a new node and adjust the neighboring pointers. Deletions simply move the head or tail pointer and detach the removed node. Because each node directly connects to both neighbors, operations at both ends remain constant time. Track the current size to enforce the capacity limit and determine isFull or isEmpty. Every operation runs in O(1) time with O(k) space for storing nodes. This approach is more flexible but has slightly higher memory overhead due to pointer storage.

Both implementations follow the core behavior of a deque: efficient insertions and removals from both ends. The difference lies in memory layout and pointer management. Circular arrays rely on index arithmetic, while linked lists rely on pointer adjustments.

Recommended for interviews: The circular array implementation is usually the expected answer. It demonstrates understanding of circular buffers, modular arithmetic, and memory efficiency. The linked list approach still satisfies the requirements and shows solid knowledge of pointer manipulation, but interviewers often prefer the array solution because it avoids extra node allocations and mirrors how real systems implement bounded deques.

Approach 1: Using Circular Array

This approach involves using a fixed-size array to represent the deque. We'll maintain two indices, front and rear, to manage the current front and last positions in the deque. Operations like insertions and deletions are performed by adjusting these indices while ensuring they wrap around using the modulo operation as necessary to remain within the array bounds.

Python

class MyCircularDeque:
    def __init__(self, k: int):
        self.data = [-1] * k
        self.front = 0
        self.rear = 0
        self.size = 0
        self.capacity = k

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

    def insertLast(self, value: int) -> bool:
        if self.isFull():
            return False
        self.data[self.rear] = value
        self.rear = (self.rear + 1) % self.capacity
        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.rear = (self.rear - 1 + self.capacity) % self.capacity
        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
        return self.data[(self.rear - 1 + self.capacity) % self.capacity]

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

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

Java

class MyCircularDeque {
    private int[] data;
    private int front;
    private int rear;
    private int size;
    private int capacity;

    public MyCircularDeque(int k) {
        data = new int[k];
        front = 0;
        rear = 0;
        size = 0;
        capacity = k;
    }

    public boolean insertFront(int value) {
        if (isFull()) return false;
        front = (front - 1 + capacity) % capacity;
        data[front] = value;
        size++;
        return true;
    }

    public boolean insertLast(int value) {
        if (isFull()) return false;
        data[rear] = value;
        rear = (rear + 1) % capacity;
        size++;
        return true;
    }

    public boolean deleteFront() {
        if (isEmpty()) return false;
        front = (front + 1) % capacity;
        size--;
        return true;
    }

    public boolean deleteLast() {
        if (isEmpty()) return false;
        rear = (rear - 1 + capacity) % capacity;
        size--;
        return true;
    }

    public int getFront() {
        if (isEmpty()) return -1;
        return data[front];
    }

    public int getRear() {
        if (isEmpty()) return -1;
        return data[(rear - 1 + capacity) % capacity];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }
}

C++

#include <vector>
using namespace std;

class MyCircularDeque {
    vector<int> data;
    int front;
    int rear;
    int size;
    int capacity;

public:
    MyCircularDeque(int k) : data(k), front(0), rear(0), size(0), capacity(k) {}

    bool insertFront(int value) {
        if (isFull()) return false;
        front = (front - 1 + capacity) % capacity;
        data[front] = value;
        size++;
        return true;
    }

    bool insertLast(int value) {
        if (isFull()) return false;
        data[rear] = value;
        rear = (rear + 1) % capacity;
        size++;
        return true;
    }

    bool deleteFront() {
        if (isEmpty()) return false;
        front = (front + 1) % capacity;
        size--;
        return true;
    }

    bool deleteLast() {
        if (isEmpty()) return false;
        rear = (rear - 1 + capacity) % capacity;
        size--;
        return true;
    }

    int getFront() {
        if (isEmpty()) return -1;
        return data[front];
    }

    int getRear() {
        if (isEmpty()) return -1;
        return data[(rear - 1 + capacity) % capacity];
    }

    bool isEmpty() {
        return size == 0;
    }

    bool isFull() {
        return size == capacity;
    }
};

JavaScript

class MyCircularDeque {
    constructor(k) {
        this.data = new Array(k).fill(-1);
        this.front = 0;
        this.rear = 0;
        this.size = 0;
        this.capacity = k;
    }

    insertFront(value) {
        if (this.isFull()) return false;
        this.front = (this.front - 1 + this.capacity) % this.capacity;
        this.data[this.front] = value;
        this.size++;
        return true;
    }

    insertLast(value) {
        if (this.isFull()) return false;
        this.data[this.rear] = value;
        this.rear = (this.rear + 1) % this.capacity;
        this.size++;
        return true;
    }

    deleteFront() {
        if (this.isEmpty()) return false;
        this.front = (this.front + 1) % this.capacity;
        this.size--;
        return true;
    }

    deleteLast() {
        if (this.isEmpty()) return false;
        this.rear = (this.rear - 1 + this.capacity) % this.capacity;
        this.size--;
        return true;
    }

    getFront() {
        if (this.isEmpty()) return -1;
        return this.data[this.front];
    }

    getRear() {
        if (this.isEmpty()) return -1;
        return this.data[(this.rear - 1 + this.capacity) % this.capacity];
    }

    isEmpty() {
        return this.size === 0;
    }

    isFull() {
        return this.size === this.capacity;
    }
}

#include <stdbool.h>

typedef struct {
    int* data;
    int front;
    int rear;
    int size;
    int capacity;
} MyCircularDeque;

MyCircularDeque* myCircularDequeCreate(int k) {
    MyCircularDeque* obj = (MyCircularDeque*) malloc(sizeof(MyCircularDeque));
    obj->data = (int*) malloc(sizeof(int) * k);
    obj->front = 0;
    obj->rear = 0;
    obj->size = 0;
    obj->capacity = k;
    return obj;
}

bool myCircularDequeInsertFront(MyCircularDeque* obj, int value) {
    if (obj->size == obj->capacity) return false;
    obj->front = (obj->front - 1 + obj->capacity) % obj->capacity;
    obj->data[obj->front] = value;
    obj->size++;
    return true;
}

bool myCircularDequeInsertLast(MyCircularDeque* obj, int value) {
    if (obj->size == obj->capacity) return false;
    obj->data[obj->rear] = value;
    obj->rear = (obj->rear + 1) % obj->capacity;
    obj->size++;
    return true;
}

bool myCircularDequeDeleteFront(MyCircularDeque* obj) {
    if (obj->size == 0) return false;
    obj->front = (obj->front + 1) % obj->capacity;
    obj->size--;
    return true;
}

bool myCircularDequeDeleteLast(MyCircularDeque* obj) {
    if (obj->size == 0) return false;
    obj->rear = (obj->rear - 1 + obj->capacity) % obj->capacity;
    obj->size--;
    return true;
}

int myCircularDequeGetFront(MyCircularDeque* obj) {
    if (obj->size == 0) return -1;
    return obj->data[obj->front];
}

int myCircularDequeGetRear(MyCircularDeque* obj) {
    if (obj->size == 0) return -1;
    return obj->data[(obj->rear - 1 + obj->capacity) % obj->capacity];
}

bool myCircularDequeIsEmpty(MyCircularDeque* obj) {
    return obj->size == 0;
}

bool myCircularDequeIsFull(MyCircularDeque* obj) {
    return obj->size == obj->capacity;
}

void myCircularDequeFree(MyCircularDeque* obj) {
    free(obj->data);
    free(obj);
}

public class MyCircularDeque {
    private int[] data;
    private int front;
    private int rear;
    private int size;
    private int capacity;

    public MyCircularDeque(int k) {
        data = new int[k];
        front = 0;
        rear = 0;
        size = 0;
        capacity = k;
    }

    public bool InsertFront(int value) {
        if (IsFull()) return false;
        front = (front - 1 + capacity) % capacity;
        data[front] = value;
        size++;
        return true;
    }

    public bool InsertLast(int value) {
        if (IsFull()) return false;
        data[rear] = value;
        rear = (rear + 1) % capacity;
        size++;
        return true;
    }

    public bool DeleteFront() {
        if (IsEmpty()) return false;
        front = (front + 1) % capacity;
        size--;
        return true;
    }

    public bool DeleteLast() {
        if (IsEmpty()) return false;
        rear = (rear - 1 + capacity) % capacity;
        size--;
        return true;
    }

    public int GetFront() {
        if (IsEmpty()) return -1;
        return data[front];
    }

    public int GetRear() {
        if (IsEmpty()) return -1;
        return data[(rear - 1 + capacity) % capacity];
    }

    public bool IsEmpty() {
        return size == 0;
    }

    public bool IsFull() {
        return size == capacity;
    }
}

Python solution uses a list to simulate the circular deque operations. It utilizes the modulo operation to keep track of the indices effectively and allows wrap-around of front and rear. The solution checks if the deque is full or empty before insertions or deletions, respectively.

Complexity

Time Complexity: O(1) for all operations.
Space Complexity: O(k), where k is the capacity of the deque.

Try this approach in the editor

Approach 2: Using Linked List

This approach makes use of a doubly linked list to implement the deque. This is particularly effective because it offers dynamic memory usage which can grow or shrink with the number of elements, instead of relying on a pre-allocated fixed-size structure as with arrays.

Python

class Node:
    def __init__(self, value=None):
        self.value = value
        self.next = None
        self.prev = None

class MyCircularDeque:
    def __init__(self, k):
        self.front = None
        self.rear = None
        self.size = 0
        self.capacity = k

    def insertFront(self, value):
        if self.isFull():
            return False
        node = Node(value)
        node.next = self.front
        if self.front:
            self.front.prev = node
        self.front = node
        if self.rear is None:
            self.rear = node
        self.size += 1
        return True

    def insertLast(self, value):
        if self.isFull():
            return False
        node = Node(value)
        node.prev = self.rear
        if self.rear:
            self.rear.next = node
        self.rear = node
        if self.front is None:
            self.front = node
        self.size += 1
        return True

    def deleteFront(self):
        if self.isEmpty():
            return False
        self.front = self.front.next
        if self.front:
            self.front.prev = None
        else:
            self.rear = None
        self.size -= 1
        return True

    def deleteLast(self):
        if self.isEmpty():
            return False
        self.rear = self.rear.prev
        if self.rear:
            self.rear.next = None
        else:
            self.front = None
        self.size -= 1
        return True

    def getFront(self):
        return -1 if self.isEmpty() else self.front.value

    def getRear(self):
        return -1 if self.isEmpty() else self.rear.value

    def isEmpty(self):
        return self.size == 0

    def isFull(self):
        return self.size == self.capacity

Java

class Node {
    int value;
    Node next;
    Node prev;
    Node(int value) {
        this.value = value;
    }
}

class MyCircularDeque {
    Node front;
    Node rear;
    int size;
    int capacity;

    public MyCircularDeque(int k) {
        this.size = 0;
        this.capacity = k;
        this.front = this.rear = null;
    }

    public boolean insertFront(int value) {
        if (isFull()) return false;
        Node node = new Node(value);
        node.next = front;
        if (front != null) front.prev = node;
        front = node;
        if (rear == null) rear = node;
        size++;
        return true;
    }

    public boolean insertLast(int value) {
        if (isFull()) return false;
        Node node = new Node(value);
        node.prev = rear;
        if (rear != null) rear.next = node;
        rear = node;
        if (front == null) front = node;
        size++;
        return true;
    }

    public boolean deleteFront() {
        if (isEmpty()) return false;
        front = front.next;
        if (front != null) front.prev = null;
        else rear = null;
        size--;
        return true;
    }

    public boolean deleteLast() {
        if (isEmpty()) return false;
        rear = rear.prev;
        if (rear != null) rear.next = null;
        else front = null;
        size--;
        return true;
    }

    public int getFront() {
        return isEmpty() ? -1 : front.value;
    }

    public int getRear() {
        return isEmpty() ? -1 : rear.value;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }
}

C++

#include <algorithm>
using namespace std;

class Node {
public:
    int value;
    Node* next;
    Node* prev;
    Node(int value): value(value), next(nullptr), prev(nullptr) {}
};

class MyCircularDeque {
    Node* front;
    Node* rear;
    int size;
    int capacity;

public:
    MyCircularDeque(int k): size(0), capacity(k), front(nullptr), rear(nullptr) {}

    bool insertFront(int value) {
        if (isFull()) return false;
        Node* node = new Node(value);
        node->next = front;
        if (front != nullptr) front->prev = node;
        front = node;
        if (rear == nullptr) rear = node;
        size++;
        return true;
    }

    bool insertLast(int value) {
        if (isFull()) return false;
        Node* node = new Node(value);
        node->prev = rear;
        if (rear != nullptr) rear->next = node;
        rear = node;
        if (front == nullptr) front = node;
        size++;
        return true;
    }

    bool deleteFront() {
        if (isEmpty()) return false;
        Node* temp = front;
        front = front->next;
        if (front != nullptr) front->prev = nullptr;
        else rear = nullptr;
        delete temp;
        size--;
        return true;
    }

    bool deleteLast() {
        if (isEmpty()) return false;
        Node* temp = rear;
        rear = rear->prev;
        if (rear != nullptr) rear->next = nullptr;
        else front = nullptr;
        delete temp;
        size--;
        return true;
    }

    int getFront() {
        return isEmpty() ? -1 : front->value;
    }

    int getRear() {
        return isEmpty() ? -1 : rear->value;
    }

    bool isEmpty() {
        return size == 0;
    }

    bool isFull() {
        return size == capacity;
    }
};

JavaScript

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

class MyCircularDeque {
    constructor(k) {
        this.front = null;
        this.rear = null;
        this.size = 0;
        this.capacity = k;
    }

    insertFront(value) {
        if (this.isFull()) return false;
        const node = new Node(value);
        node.next = this.front;
        if (this.front) this.front.prev = node;
        this.front = node;
        if (!this.rear) this.rear = node;
        this.size++;
        return true;
    }

    insertLast(value) {
        if (this.isFull()) return false;
        const node = new Node(value);
        node.prev = this.rear;
        if (this.rear) this.rear.next = node;
        this.rear = node;
        if (!this.front) this.front = node;
        this.size++;
        return true;
    }

    deleteFront() {
        if (this.isEmpty()) return false;
        this.front = this.front.next;
        if (this.front) this.front.prev = null;
        else this.rear = null;
        this.size--;
        return true;
    }

    deleteLast() {
        if (this.isEmpty()) return false;
        this.rear = this.rear.prev;
        if (this.rear) this.rear.next = null;
        else this.front = null;
        this.size--;
        return true;
    }

    getFront() {
        return this.isEmpty() ? -1 : this.front.value;
    }

    getRear() {
        return this.isEmpty() ? -1 : this.rear.value;
    }

    isEmpty() {
        return this.size === 0;
    }

    isFull() {
        return this.size === this.capacity;
    }
}

#include <stdbool.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *next;
    struct Node *prev;
} Node;

typedef struct {
    Node *front;
    Node *rear;
    int size;
    int capacity;
} MyCircularDeque;

MyCircularDeque* myCircularDequeCreate(int k) {
    MyCircularDeque* obj = (MyCircularDeque*) malloc(sizeof(MyCircularDeque));
    obj->front = obj->rear = NULL;
    obj->size = 0;
    obj->capacity = k;
    return obj;
}

bool myCircularDequeInsertFront(MyCircularDeque* obj, int value) {
    if (obj->size == obj->capacity) return false;
    Node *node = (Node*) malloc(sizeof(Node));
    node->value = value;
    node->next = obj->front;
    node->prev = NULL;
    if (obj->front != NULL) {
        obj->front->prev = node;
    }
    obj->front = node;
    if (obj->rear == NULL) {
        obj->rear = node;
    }
    obj->size++;
    return true;
}

bool myCircularDequeInsertLast(MyCircularDeque* obj, int value) {
    if (obj->size == obj->capacity) return false;
    Node *node = (Node*) malloc(sizeof(Node));
    node->value = value;
    node->prev = obj->rear;
    node->next = NULL;
    if (obj->rear != NULL) {
        obj->rear->next = node;
    }
    obj->rear = node;
    if (obj->front == NULL) {
        obj->front = node;
    }
    obj->size++;
    return true;
}

bool myCircularDequeDeleteFront(MyCircularDeque* obj) {
    if (obj->size == 0) return false;
    Node *temp = obj->front;
    obj->front = obj->front->next;
    if (obj->front != NULL) {
        obj->front->prev = NULL;
    } else {
        obj->rear = NULL;
    }
    free(temp);
    obj->size--;
    return true;
}

bool myCircularDequeDeleteLast(MyCircularDeque* obj) {
    if (obj->size == 0) return false;
    Node *temp = obj->rear;
    obj->rear = obj->rear->prev;
    if (obj->rear != NULL) {
        obj->rear->next = NULL;
    } else {
        obj->front = NULL;
    }
    free(temp);
    obj->size--;
    return true;
}

int myCircularDequeGetFront(MyCircularDeque* obj) {
    return (obj->size == 0) ? -1 : obj->front->value;
}

int myCircularDequeGetRear(MyCircularDeque* obj) {
    return (obj->size == 0) ? -1 : obj->rear->value;
}

bool myCircularDequeIsEmpty(MyCircularDeque* obj) {
    return obj->size == 0;
}

bool myCircularDequeIsFull(MyCircularDeque* obj) {
    return obj->size == obj->capacity;
}

void myCircularDequeFree(MyCircularDeque* obj) {
    while (obj->front != NULL) {
        Node *temp = obj->front;
        obj->front = obj->front->next;
        free(temp);
    }
    free(obj);
}

public class Node {
    public int Value;
    public Node Next;
    public Node Prev;
    public Node(int value) {
        Value = value;
        Next = Prev = null;
    }
}

public class MyCircularDeque {
    private Node front;
    private Node rear;
    private int size;
    private int capacity;

    public MyCircularDeque(int k) {
        front = rear = null;
        size = 0;
        capacity = k;
    }

    public bool InsertFront(int value) {
        if (IsFull()) return false;
        Node node = new Node(value);
        node.Next = front;
        if (front != null) front.Prev = node;
        front = node;
        if (rear == null) rear = node;
        size++;
        return true;
    }

    public bool InsertLast(int value) {
        if (IsFull()) return false;
        Node node = new Node(value);
        node.Prev = rear;
        if (rear != null) rear.Next = node;
        rear = node;
        if (front == null) front = node;
        size++;
        return true;
    }

    public bool DeleteFront() {
        if (IsEmpty()) return false;
        front = front.Next;
        if (front != null) front.Prev = null;
        else rear = null;
        size--;
        return true;
    }

    public bool DeleteLast() {
        if (IsEmpty()) return false;
        rear = rear.Prev;
        if (rear != null) rear.Next = null;
        else front = null;
        size--;
        return true;
    }

    public int GetFront() {
        return IsEmpty() ? -1 : front.Value;
    }

    public int GetRear() {
        return IsEmpty() ? -1 : rear.Value;
    }

    public bool IsEmpty() {
        return size == 0;
    }

    public bool IsFull() {
        return size == capacity;
    }
}

Python's linked list approach enables a flexible allocation for deques with nodes connecting backward and forward, simplifying insertions/deletions by just adjusting node pointers. Each operation reacts in constant time, not hindered by array resizing constraints.

Complexity

Time Complexity: O(1) for every operation.
Space Complexity: O(n), with n nodes currently maintained.

Try this approach in the editor

Approach 3: Array

We can use an array to implement the circular deque. We maintain a pointer front pointing to the front of the queue, a variable size representing the number of elements in the queue, and a variable capacity representing the queue's capacity. We use an array q to store the elements.

When insertFront is called, we first check if the queue is full; if so, return false. Otherwise, we move front one position forward (using modular arithmetic for circular wrapping), insert the new element at front, and increment size by 1.

When insertLast is called, we first check if the queue is full; if so, return false. Otherwise, we compute the insertion position (using front and size), insert the new element there, and increment size by 1.

When deleteFront is called, we first check if the queue is empty; if so, return false. Otherwise, we move front one position backward (using modular arithmetic for circular wrapping) and decrement size by 1.

When deleteLast is called, we first check if the queue is empty; if so, return false. Otherwise, we decrement size by 1.

When getFront is called, we first check if the queue is empty; if so, return -1. Otherwise, we return q[front].

When getRear is called, we first check if the queue is empty; if so, return -1. Otherwise, we compute the position of the rear element (using front and size) and return the element at that position.

When isEmpty is called, we check whether size equals 0.

When isFull is called, we check whether size equals capacity.

All operations above have a time complexity of O(1) and a space complexity of O(k), where k is the capacity of the deque.

TypeScript

class MyCircularDeque {
    private vals: number[];
    private length: number;
    private size: number;
    private start: number;
    private end: number;

    constructor(k: number) {
        this.vals = new Array(k).fill(0);
        this.start = 0;
        this.end = 0;
        this.length = 0;
        this.size = k;
    }

    insertFront(value: number): boolean {
        if (this.isFull()) {
            return false;
        }

        if (this.start === 0) {
            this.start = this.size - 1;
        } else {
            this.start--;
        }
        this.vals[this.start] = value;
        this.length++;
        return true;
    }

    insertLast(value: number): boolean {
        if (this.isFull()) {
            return false;
        }

        this.vals[this.end] = value;
        this.length++;
        if (this.end + 1 === this.size) {
            this.end = 0;
        } else {
            this.end++;
        }
        return true;
    }

    deleteFront(): boolean {
        if (this.isEmpty()) {
            return false;
        }

        if (this.start + 1 === this.size) {
            this.start = 0;
        } else {
            this.start++;
        }
        this.length--;
        return true;
    }

    deleteLast(): boolean {
        if (this.isEmpty()) {
            return false;
        }

        if (this.end === 0) {
            this.end = this.size - 1;
        } else {
            this.end--;
        }
        this.length--;
        return true;
    }

    getFront(): number {
        if (this.isEmpty()) {
            return -1;
        }

        return this.vals[this.start];
    }

    getRear(): number {
        if (this.isEmpty()) {
            return -1;
        }

        if (this.end === 0) {
            return this.vals[this.size - 1];
        }
        return this.vals[this.end - 1];
    }

    isEmpty(): boolean {
        return this.length === 0;
    }

    isFull(): boolean {
        return this.length === this.size;
    }
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * var obj = new MyCircularDeque(k)
 * var param_1 = obj.insertFront(value)
 * var param_2 = obj.insertLast(value)
 * var param_3 = obj.deleteFront()
 * var param_4 = obj.deleteLast()
 * var param_5 = obj.getFront()
 * var param_6 = obj.getRear()
 * var param_7 = obj.isEmpty()
 * var param_8 = obj.isFull()
 */

type MyCircularDeque struct {
	q        []int
	size     int
	front    int
	capacity int
}

func Constructor(k int) MyCircularDeque {
	q := make([]int, k)
	return MyCircularDeque{q, 0, 0, k}
}

func (this *MyCircularDeque) InsertFront(value int) bool {
	if this.IsFull() {
		return false
	}
	if !this.IsEmpty() {
		this.front = (this.front - 1 + this.capacity) % this.capacity
	}
	this.q[this.front] = value
	this.size++
	return true
}

func (this *MyCircularDeque) InsertLast(value int) bool {
	if this.IsFull() {
		return false
	}
	idx := (this.front + this.size) % this.capacity
	this.q[idx] = value
	this.size++
	return true
}

func (this *MyCircularDeque) DeleteFront() bool {
	if this.IsEmpty() {
		return false
	}
	this.front = (this.front + 1) % this.capacity
	this.size -= 1
	return true
}

func (this *MyCircularDeque) DeleteLast() bool {
	if this.IsEmpty() {
		return false
	}
	this.size -= 1
	return true
}

func (this *MyCircularDeque) GetFront() int {
	if this.IsEmpty() {
		return -1
	}
	return this.q[this.front]
}

func (this *MyCircularDeque) GetRear() int {
	if this.IsEmpty() {
		return -1
	}
	return this.q[(this.front+this.size-1)%this.capacity]
}

func (this *MyCircularDeque) IsEmpty() bool {
	return this.size == 0
}

func (this *MyCircularDeque) IsFull() bool {
	return this.size == this.capacity
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * obj := Constructor(k);
 * param_1 := obj.InsertFront(value);
 * param_2 := obj.InsertLast(value);
 * param_3 := obj.DeleteFront();
 * param_4 := obj.DeleteLast();
 * param_5 := obj.GetFront();
 * param_6 := obj.GetRear();
 * param_7 := obj.IsEmpty();
 * param_8 := obj.IsFull();
 */

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using Circular Array	Time Complexity: O(1) for all operations. Space Complexity: O(k), where k is the capacity of the deque.
Using Linked List	Time Complexity: O(1) for every operation. Space Complexity: O(n), with n nodes currently maintained.
Array	–

Complexity analysis

Approach	Time	Space	When to Use
Circular Array	O(1) per operation	O(k)	Preferred for fixed-capacity deque implementations and interview settings due to simplicity and cache efficiency
Doubly Linked List	O(1) per operation	O(k)	Useful when dynamic node manipulation is preferred or when implementing deque behavior without array indexing

Frequently asked questions

Is Design Circular Deque easy or hard?

Design Circular Deque is classified as a Medium problem. The difficulty comes from correctly handling edge cases such as wrap-around indexing, full vs empty states, and maintaining constant-time operations for all deque methods.

Design Circular Deque Python/Java solution

Python and Java solutions typically implement the circular array approach with a fixed array, two pointers (front and rear), and a size counter. Each operation updates indices using modulo arithmetic so insertions and deletions remain O(1).

How to solve Design Circular Deque in O(1)?

Use a fixed-size circular array and track two indices representing the front and rear of the deque. Update indices using modular arithmetic when inserting or deleting elements so they wrap around the array. This avoids shifting elements and guarantees O(1) time per operation.

What is the best approach for Design Circular Deque?

The circular array approach is the most efficient and commonly expected solution. It uses modular arithmetic to wrap indices around the array, allowing insertions and deletions from both ends in O(1) time with O(k) space. This approach avoids node allocations and keeps memory contiguous.

Is Design Circular Deque asked at Google/Amazon/Meta?

Deque design and circular buffer problems frequently appear in interviews at companies like Amazon, Google, and Meta. They test understanding of data structure design, pointer/index manipulation, and constant-time operations.

What data structure is used in Design Circular Deque?

The problem can be implemented using either a circular array or a doubly linked list. A circular array uses index arithmetic to reuse array space, while a doubly linked list uses nodes with prev and next pointers to support efficient operations at both ends.

What is the time complexity of Design Circular Deque?

All required operations—insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, and isFull—run in O(1) time. Both circular array and doubly linked list implementations achieve constant-time operations because they modify only indices or pointers.

Design Circular Deque solution and explanation

The problem

Approach overview

Approach 1: Using Circular Array

Approach 2: Using Linked List

Approach 3: Array

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Design Circular Deque solution and explanation

The problem

Approach overview

Approach 1: Using Circular Array

Approach 2: Using Linked List

Approach 3: Array

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems