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.

Description Solution Video 24:55

641. Design Circular Deque

Medium65.2% acceptance5 companies

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.

Asked at 5 companies

Snowflake Goldman Sachs

Google Amazon Meta

Topics

24:55

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

Similar problems

Design Circular QueueMedium Design Front Middle Back QueueMedium

LanguageLoading editor…

1class 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:
      


31# Your MyCircularDeque object will be instantiated and called as such:
32# obj = MyCircularDeque(k)
33# param_1 = obj.insertFront(value)
34# param_2 = obj.insertLast(value)
35# param_3 = obj.deleteFront()
36# param_4 = obj.deleteLast()
37# param_5 = obj.getFront()
38# param_6 = obj.getRear()
39# param_7 = obj.isEmpty()
40# param_8 = obj.isFull()

Starter codePython 3Spaces: 4

Examples

Case 1

Input

["MyCircularDeque","insertLast","insertLast","insertFront","insertFront","getRear","isFull","deleteLast","insertFront","getFront"]
[[3],[1],[2],[3],[4],[],[],[],[4],[]]

Your code is saved on this device.Solution