Design Circular Deque - Solution & Explanation

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.

MediumArray Linked List Design Queue34 min readAsked at: Amazon, Goldman Sachs, Meta +2

Practice this problem

Problem Statement

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.

This implementation uses a circular array to manage the deque operations. The array is of fixed size, calculated by the given capacity, and follows the circular method to use the front and rear indices effectively. The modulo operation is crucial to wrap around these indices and prevent them from exceeding array bounds.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(1) for each operation.
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.

Using a linked list in C allows dynamic memory management for each element in the deque. Nodes are created or deleted dynamically, with pointers next and prev facilitating easy front and rear operations.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(1) for all operations.
Space Complexity: O(n), where n is the number of elements currently in the deque (potentially more efficient if n is much less than the initial capacity).

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.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Using Circular Array	Time Complexity: O(1) for each operation. Space Complexity: O(k), where k is the capacity of the deque.
Using Linked List	Time Complexity: O(1) for all operations. Space Complexity: O(n), where n is the number of elements currently in the deque (potentially more efficient if n is much less than the initial capacity).
Array	—

Detailed 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

Video Solution

Design Circular Deque | Simplest Explanation | 2 Ways | Leetcode 641 | codestorywithMIK • codestorywithMIK • 8,236 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Design Circular Deque with our built-in code editor and test cases.

Practice on FleetCode

Design Circular Queue

Design Front Middle Back Queue

Problem Info

DifficultyMedium

Acceptance64.6%

Approaches3

Reading time34 min

Asked at

Amazon Goldman Sachs Meta Snowflake Google

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Using Circular Array

Code

Complexity

Approach 2: Using Linked List

Code

Complexity

Approach 3: Array

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents