Design Circular Deque — Solution in Python, Java & C++
Design Circular Deque solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Design Circular Deque is a medium coding problem on arrays and queue, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Queue
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Implement a circular double-ended queue of fixed capacity, where elements can be added and removed at both ends, without using a built-in deque. Write the class MyCircularDeque:
MyCircularDeque(int k)creates a deque that holds at mostkelements.boolean insertFront(int value)/boolean insertLast(int value)addvalueat the front / back; they returntrueon success andfalseif the deque is full.boolean deleteFront()/boolean deleteLast()remove the front / back element; they returntrueon success andfalseif the deque is empty.int getFront()/int getRear()return the front / back element, or-1if the deque is empty.boolean isEmpty()/boolean isFull()report whether the deque is empty / full.
The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.
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: Capacity 3 holds [3,1,2]; inserting 4 at the front fails. The rear is 2. After deleteLast the deque is [3,1], so 4 fits at the front and becomes getFront.
Example 2
Input: ["MyCircularDeque","getFront","deleteLast","insertFront","insertLast","getRear","deleteFront","getFront","isEmpty"]
[[2],[],[],[5],[8],[],[],[],[]]
Output: [null,-1,false,true,true,8,true,8,false]
Explanation: An empty deque answers -1 and refuses to delete. After [5,8], the rear is 8; deleting the front leaves 8 at both ends.
Constraints
1 <= k <= 10000 <= value <= 1000At most 2000 calls are made to insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty and isFull
Hints for Design Circular Deque
Hint 1
This is a circular queue that can also grow and shrink at the front.
Hint 2
Keep
front(index of the first element) andcountin an array of sizek; the last element is at(front + count - 1) % k.Hint 3
insertFront moves
frontone step back —(front - 1 + k) % kkeeps it non-negative — and writes there; deleteFront moves it one step forward. The back end only changescount.
How to solve Design Circular Deque
A ring buffer with a front index and a count. Both ends are reachable in O(1): the front is front, the back is front + count - 1, each taken modulo k; adding at the front steps front backwards around the ring.
Approach
- Store
bufof sizek,front = 0,count = 0. insertFront(v): if full return false;front = (front - 1 + k) % k,buf[front] = v,count++.insertLast(v): if full return false;buf[(front + count) % k] = v,count++.deleteFront(): if empty return false;front = (front + 1) % k,count--.deleteLast(): if empty return false;count--.getFront()isbuf[front],getRear()isbuf[(front + count - 1) % k](each -1 when empty);isEmpty/isFullcomparecountwith 0 /k.
Why it works
The elements always occupy the count consecutive ring positions starting at front. Each operation either extends or shrinks that run by one slot at the appropriate end and leaves every other element in place, so the deque order is kept and no element is ever moved.
Complexity
- Time —
O(1) per operation - Space —
O(k)
Pitfalls
(front - 1) % kis negative forfront = 0in C, C++, Java, Go, JavaScript and others — addkfirst.- Return -1 from getFront / getRear on an empty deque.
Reference solution
Python
class MyCircularDeque:
def __init__(self, k: int):
self.buf = [0] * k
self.k = k
self.front = 0
self.count = 0
def insertFront(self, value: int) -> bool:
if self.count == self.k:
return False
self.front = (self.front - 1) % self.k
self.buf[self.front] = value
self.count += 1
return True
def insertLast(self, value: int) -> bool:
if self.count == self.k:
return False
self.buf[(self.front + self.count) % self.k] = value
self.count += 1
return True
def deleteFront(self) -> bool:
if self.count == 0:
return False
self.front = (self.front + 1) % self.k
self.count -= 1
return True
def deleteLast(self) -> bool:
if self.count == 0:
return False
self.count -= 1
return True
def getFront(self) -> int:
return self.buf[self.front] if self.count else -1
def getRear(self) -> int:
return self.buf[(self.front + self.count - 1) % self.k] if self.count else -1
def isEmpty(self) -> bool:
return self.count == 0
def isFull(self) -> bool:
return self.count == self.kJava
class MyCircularDeque {
private int[] buf;
private int k, front = 0, count = 0;
public MyCircularDeque(int k) {
this.k = k;
buf = new int[k];
}
public boolean insertFront(int value) {
if (count == k) return false;
front = (front - 1 + k) % k;
buf[front] = value;
count++;
return true;
}
public boolean insertLast(int value) {
if (count == k) return false;
buf[(front + count) % k] = value;
count++;
return true;
}
public boolean deleteFront() {
if (count == 0) return false;
front = (front + 1) % k;
count--;
return true;
}
public boolean deleteLast() {
if (count == 0) return false;
count--;
return true;
}
public int getFront() {
return count == 0 ? -1 : buf[front];
}
public int getRear() {
return count == 0 ? -1 : buf[(front + count - 1) % k];
}
public boolean isEmpty() {
return count == 0;
}
public boolean isFull() {
return count == k;
}
}C++
class MyCircularDeque {
vector<int> buf;
int k, front = 0, count = 0;
public:
MyCircularDeque(int k) : buf(k), k(k) {}
bool insertFront(int value) {
if (count == k) return false;
front = (front - 1 + k) % k;
buf[front] = value;
count++;
return true;
}
bool insertLast(int value) {
if (count == k) return false;
buf[(front + count) % k] = value;
count++;
return true;
}
bool deleteFront() {
if (count == 0) return false;
front = (front + 1) % k;
count--;
return true;
}
bool deleteLast() {
if (count == 0) return false;
count--;
return true;
}
int getFront() {
return count == 0 ? -1 : buf[front];
}
int getRear() {
return count == 0 ? -1 : buf[(front + count - 1) % k];
}
bool isEmpty() {
return count == 0;
}
bool isFull() {
return count == k;
}
};JavaScript
var MyCircularDeque = function(k) {
this.k = k;
this.buf = [];
this.front = 0;
this.count = 0;
};
MyCircularDeque.prototype.insertFront = function(value) {
if (this.count === this.k) return false;
this.front = (this.front - 1 + this.k) % this.k;
this.buf[this.front] = value;
this.count++;
return true;
};
MyCircularDeque.prototype.insertLast = function(value) {
if (this.count === this.k) return false;
this.buf[(this.front + this.count) % this.k] = value;
this.count++;
return true;
};
MyCircularDeque.prototype.deleteFront = function() {
if (this.count === 0) return false;
this.front = (this.front + 1) % this.k;
this.count--;
return true;
};
MyCircularDeque.prototype.deleteLast = function() {
if (this.count === 0) return false;
this.count--;
return true;
};
MyCircularDeque.prototype.getFront = function() {
return this.count === 0 ? -1 : this.buf[this.front];
};
MyCircularDeque.prototype.getRear = function() {
return this.count === 0 ? -1 : this.buf[(this.front + this.count - 1) % this.k];
};
MyCircularDeque.prototype.isEmpty = function() {
return this.count === 0;
};
MyCircularDeque.prototype.isFull = function() {
return this.count === this.k;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Queues and Deques