Log inSign up
mediumLeetCodeNot Started

Design Circular Deque

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Queue
Solve on LeetCode
Lesson

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. Indicates true on success. - boolean insertLast() Adds an item at the rear of Deque. Indicates true on success. - boolean deleteFront() Deletes an item from the front of Deque. Indicates true on success. - boolean deleteLast() Deletes an item from the rear of Deque. Indicates true on success. - int getFront() Returns the front item from the Deque. If the deque is empty, return -1. - int getRear() Returns the last item from Deque. If the deque is empty, return -1. - boolean isEmpty() Returns true if the deque is empty. - boolean isFull() Returns true if the deque is full.

Example 1 · Standard Circular Deque Operations:

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.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Design Circular Queue
  • Modulo Arithmetic for Negative Indices

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master bidirectional modulo pointer movement for ring buffers.
  • Handle negative index wrap-around in languages where % preserves negative signs.
  • Understand why circular deques power core data structures like Python's collections.deque.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Bidirectional insertion and deletion within fixed capacity limits.
  • Sliding window monotonic deque tracking or buffer caches.

Algorithmic Decision Tree:

  • Maintain front index and count variable.
  • Wrap counter-clockwise: (idx - 1 + capacity) % capacity.
  • Wrap clockwise: (idx + 1) % capacity.

Connected Patterns:

Design Circular QueueSliding Window MaximumDesign Front Middle Back Queue

1. Brute Force — Dynamic Array with Front Shift

Intuition

Store items in an array, pushing and unshifting directly.

Algorithm

  1. Step 1: On insertFront(x), unshift x at index 0 if length < k.
  2. Step 2: On insertLast(x), push x at end if length < k.
  3. Step 3: On deleteFront(), remove index 0; on deleteLast(), pop end.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class MyCircularDeque {
7private:
8 vector<int> arr;
9 int cap;
10public:
11 MyCircularDeque(int k) : cap(k) {}
12
13 bool insertFront(int value) {
14 if (arr.size() == cap) return false;
15 arr.insert(arr.begin(), value);
16 return true;
17 }
18
19 bool insertLast(int value) {
20 if (arr.size() == cap) return false;
21 arr.push_back(value);
22 return true;
23 }
24
25 bool deleteFront() {
26 if (arr.empty()) return false;
27 arr.erase(arr.begin());
28 return true;
29 }
30
31 bool deleteLast() {
32 if (arr.empty()) return false;
33 arr.pop_back();
34 return true;
35 }
36
37 int getFront() {
38 return arr.empty() ? -1 : arr.front();
39 }
40
41 int getRear() {
42 return arr.empty() ? -1 : arr.back();
43 }
44
45 bool isEmpty() {
46 return arr.empty();
47 }
48
49 bool isFull() {
50 return arr.size() == cap;
51 }
52};
53
54int main() {
55 MyCircularDeque dq(3);
56 cout << dq.insertLast(1) << endl; // 1
57 cout << dq.insertLast(2) << endl; // 1
58 cout << dq.insertFront(3) << endl; // 1
59 cout << dq.getFront() << endl; // 3
60 cout << dq.getRear() << endl; // 2
61 return 0;
62}

Time & Space Complexity

  • Time complexity: Front ops: O(N), Rear ops: O(1) — Array unshift/shift operations copy all N elements.
  • Space complexity: O(K) — Stores K elements.

Why Brute Force Doesn't Scale:

A stream of 105 alternating front/last operations will time out on dynamic lists.

Fixed ring buffer runs 105 operations in ~3ms.

2. Better — Doubly Linked List with Sentinel Pointers

Intuition

Insert between head and head.next for Front; insert between tail.prev and tail for Rear.

Algorithm

  1. Step 1: Maintain dummy head and dummy tail nodes connected to each other.
  2. Step 2: insertFront: insert node between head and head.next.
  3. Step 3: insertLast: insert node between tail.prev and tail.
  4. Step 4: deleteFront: remove head.next; deleteLast: remove tail.prev.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct DNode {
6 int val;
7 DNode* prev;
8 DNode* next;
9 DNode(int v) : val(v), prev(nullptr), next(nullptr) {}
10};
11
12class MyCircularDeque {
13private:
14 DNode* head;
15 DNode* tail;
16 int cap, count;
17public:
18 MyCircularDeque(int k) : cap(k), count(0) {
19 head = new DNode(0);
20 tail = new DNode(0);
21 head->next = tail;
22 tail->prev = head;
23 }
24
25 bool insertFront(int value) {
26 if (count == cap) return false;
27 DNode* node = new DNode(value);
28 node->next = head->next;
29 node->prev = head;
30 head->next->prev = node;
31 head->next = node;
32 count++;
33 return true;
34 }
35
36 bool insertLast(int value) {
37 if (count == cap) return false;
38 DNode* node = new DNode(value);
39 node->prev = tail->prev;
40 node->next = tail;
41 tail->prev->next = node;
42 tail->prev = node;
43 count++;
44 return true;
45 }
46
47 bool deleteFront() {
48 if (count == 0) return false;
49 DNode* del = head->next;
50 head->next = del->next;
51 del->next->prev = head;
52 delete del;
53 count--;
54 return true;
55 }
56
57 bool deleteLast() {
58 if (count == 0) return false;
59 DNode* del = tail->prev;
60 tail->prev = del->prev;
61 del->prev->next = tail;
62 delete del;
63 count--;
64 return true;
65 }
66
67 int getFront() {
68 return count == 0 ? -1 : head->next->val;
69 }
70
71 int getRear() {
72 return count == 0 ? -1 : tail->prev->val;
73 }
74
75 bool isEmpty() {
76 return count == 0;
77 }
78
79 bool isFull() {
80 return count == cap;
81 }
82};
83
84int main() {
85 MyCircularDeque dq(2);
86 cout << dq.insertFront(10) << endl; // 1
87 cout << dq.insertLast(20) << endl; // 1
88 cout << dq.getFront() << endl; // 10
89 cout << dq.getRear() << endl; // 20
90 return 0;
91}

Time & Space Complexity

  • Time complexity: All operations O(1) — Direct pointer insertions and deletions at dummy head and tail in O(1) time.
  • Space complexity: O(K) Node Overhead — Allocates node objects with next and prev pointers.

3. Optimal — Fixed Array with Bidirectional Modulo Pointers

Intuition

Insert Front shifts front index backwards by (front - 1 + k) % k. Insert Last places item at (front + count) % k.

Algorithm

  1. Step 1: Initialize array q[k], front = 0, count = 0.
  2. Step 2: insertFront(val): If not full, front = (front - 1 + k) % k, q[front] = val, count++.
  3. Step 3: insertLast(val): If not full, q[(front + count) % k] = val, count++.
  4. Step 4: deleteFront(): If not empty, front = (front + 1) % k, count--.
  5. Step 5: deleteLast(): If not empty, count--.

Bidirectional Ring Buffer Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
front=0, count=2
Visual state
Values and pointers at this exact step
queue
FRONT → REAR
1 (idx 0)
2 (idx 1)
Enqueue adds at the rear · Dequeue removes from the front
Decision / next transition
insertLast(1), insertLast(2)
Why this step matters

front=0, count=2.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class MyCircularDeque {
7private:
8 vector<int> q;
9 int front;
10 int count;
11 int capacity;
12
13public:
14 MyCircularDeque(int k) : capacity(k), front(0), count(0), q(k) {}
15
16 bool insertFront(int value) {
17 if (isFull()) return false;
18 front = (front - 1 + capacity) % capacity;
19 q[front] = value;
20 count++;
21 return true;
22 }
23
24 bool insertLast(int value) {
25 if (isFull()) return false;
26 q[(front + count) % capacity] = value;
27 count++;
28 return true;
29 }
30
31 bool deleteFront() {
32 if (isEmpty()) return false;
33 front = (front + 1) % capacity;
34 count--;
35 return true;
36 }
37
38 bool deleteLast() {
39 if (isEmpty()) return false;
40 count--;
41 return true;
42 }
43
44 int getFront() {
45 if (isEmpty()) return -1;
46 return q[front];
47 }
48
49 int getRear() {
50 if (isEmpty()) return -1;
51 return q[(front + count - 1) % capacity];
52 }
53
54 bool isEmpty() {
55 return count == 0;
56 }
57
58 bool isFull() {
59 return count == capacity;
60 }
61};
62
63int main() {
64 MyCircularDeque dq(3);
65 cout << dq.insertLast(1) << endl; // 1 (true)
66 cout << dq.insertLast(2) << endl; // 1 (true)
67 cout << dq.insertFront(3) << endl; // 1 (true)
68 cout << dq.insertFront(4) << endl; // 0 (false - full)
69 cout << dq.getRear() << endl; // 2
70 cout << dq.isFull() << endl; // 1 (true)
71 cout << dq.deleteLast() << endl; // 1 (true)
72 cout << dq.insertFront(4) << endl; // 1 (true)
73 cout << dq.getFront() << endl; // 4
74 return 0;
75}

Time & Space Complexity

  • Time complexity: All operations O(1) — Direct index calculations with modulo arithmetic in O(1) time.
  • Space complexity: O(K) (Contiguous Memory) — Pre-allocated array of size K.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Dynamic Array ShiftinginsertFront/deleteFront: O(N), insertLast/deleteLast: O(1)O(K)Use a regular array. Inserting or deleting at index 0 shifts all elements in O(N).Linear shifting on front operations.
2.Better — Doubly Linked List with SentinelsAll operations O(1)O(K) Node OverheadMaintain doubly linked nodes with dummy head and dummy tail.Heap allocations per node.
3.Optimal — Fixed Array with Bidirectional Modulo ArithmeticOptimalAll operations O(1)O(K) (Contiguous Memory)Single contiguous array with front pointer and count variable for bidirectional wrap-around.None. Direct arithmetic index lookups.

Common Pitfalls & Crucial Edge Cases

Forgetting `+ capacity` before modulo in insertFront

In C++ and Java, (-1) % k == -1. Omitting + capacity causes negative index runtime errors.

Advancing front on insertLast

Only insertFront and deleteFront modify the front index.

Crucial Edge Cases to Validate:

  • insertFront into empty deque — front index wraps to capacity - 1 and single element is accessible by both getFront() and getRear().
  • Repeated alternation between insertFront and deleteFront — Shifts front pointer continuously around the buffer without leaks.
  • Capacity k = 1 — Ensures front and rear operations operate on the same single slot correctly.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight the difference between C++ % (remainder) and Python % (true mathematical modulo).
  2. Explain how work-stealing thread pools (like Java ForkJoinPool) use circular deques for worker thread job queues.
  3. Walk through empty-to-full state transitions carefully with small example sizes (e.g. k=2) before writing index logic.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How do you calculate the new front index when calling insertFront()?

2.How is deleteLast() performed efficiently?

3.What is the return value of getRear() on an empty deque?

Back to DSA Sheet