LeetCode · #641

Design Circular Deque Solution

Build a fixed-capacity deque with O(1) insertion and deletion at both ends using a circular array.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #641

🏗️

Pattern

Design — Circular Array / Ring Buffer

Implement MyCircularDeque with bounded capacity k. Support insert/delete at both front and rear, plus front/rear lookups and empty/full checks.

Example

 MyCircularDeque dq = new MyCircularDeque(3);
dq.insertLast(1); // true
dq.insertLast(2); // true
dq.insertFront(3); // true
dq.insertFront(4); // false, full
dq.getRear(); // 2
dq.isFull(); // true
dq.deleteLast(); // true
dq.insertFront(4); // true
dq.getFront(); // 4 

Section Two · Brute Force

Plain Array with Shifts

Keep the logical deque packed from index 0 to size - 1. Then insertFront and deleteFront need shifts, which makes them O(n).

Problem: The whole point of a deque is O(1) operations at both ends. If front operations shift elements, the structure behaves like an inefficient list, not a deque.

Section Three · Optimal

Ring Buffer with Head + Size — O(1)

Store elements in a fixed array. Track the logical front with head and the number of elements with size. Compute positions using modulo arithmetic.

💡 Mental model: Think of seats on a carousel. The front seat marker can move backward or forward, but the riders do not shift around physically. You only update which seat counts as the front and how many riders are on the carousel.

Key formulas

Front element: data[head]
Rear element: data[(head + size - 1 + capacity) % capacity]
insertFront: move head backward first, then write
insertLast: write at (head + size) % capacity
deleteFront: move head forward
deleteLast: just reduce size

Why track size?:

If you only track head and tail, then head == tail is ambiguous: it can mean either empty or full.
A size field removes that ambiguity cleanly.

Section Four · Walkthrough

Visual Walkthrough

insertFront can wrap around to the end of the array

Section Five · Code

Code — Java & Python

Java — ring buffer deque

 class MyCircularDeque {
private final int[] data;
private final int capacity;
private int head = 0;
private int size = 0;
public MyCircularDeque(int k) {
        data = new int[k];
        capacity = k;
    }
public boolean insertFront(int value) {
if (isFull()) return false;
        head = (head - 1 + capacity) % capacity;
        data[head] = value;
        size++;
return true;
    }
public boolean insertLast(int value) {
if (isFull()) return false;
int tail = (head + size) % capacity;
        data[tail] = value;
        size++;
return true;
    }
public boolean deleteFront() {
if (isEmpty()) return false;
        head = (head + 1) % capacity;
        size--;
return true;
    }
public boolean deleteLast() {
if (isEmpty()) return false;
        size--;
return true;
    }
public int getFront() {
return isEmpty() ? -1 : data[head];
    }
public int getRear() {
if (isEmpty()) return -1;
int tail = (head + size - 1 + capacity) % capacity;
return data[tail];
    }
public boolean isEmpty() {
return size == 0;
    }
public boolean isFull() {
return size == capacity;
    }
}

Python — ring buffer deque

 class MyCircularDeque:
def __init__(self, k: int):
        self.data = [0] * k
        self.capacity = k
        self.head = 0
self.size = 0 def insertFront(self, value: int) -> bool:
if self.isFull():
return False
self.head = (self.head - 1) % self.capacity
        self.data[self.head] = value
        self.size += 1 return True def insertLast(self, value: int) -> bool:
if self.isFull():
return False
tail = (self.head + self.size) % self.capacity
        self.data[tail] = value
        self.size += 1 return True def deleteFront(self) -> bool:
if self.isEmpty():
return False
self.head = (self.head + 1) % self.capacity
        self.size -= 1 return True def deleteLast(self) -> bool:
if self.isEmpty():
return False
self.size -= 1 return True def getFront(self) -> int:
return -1 if self.isEmpty() else self.data[self.head]
def getRear(self) -> int:
if self.isEmpty():
return -1
tail = (self.head + self.size - 1) % self.capacity
return self.data[tail]
def isEmpty(self) -> bool:
return self.size == 0 def isFull(self) -> bool:
return self.size == self.capacity

Section Six · Analysis

Complexity Analysis

Approach	Time	Space
Packed array with shifts	O(n) front ops	O(k)
Ring buffer deque	O(1) all methods	O(k)

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Expected result	Why it matters
`k = 1`	Only one slot alternates between empty and full	Great for catching off-by-one bugs.
Insert into full deque	Return `false`	Must reject the write, not overwrite data.
Delete from empty deque	Return `false`	The interface uses booleans, not exceptions.
Rear after many wraparounds	Still computed by modulo	Physical positions move, logical order stays valid.

⚠ Common Mistake: Updating the array before moving head in insertFront. The correct order is: move head first, then write the value there.

← Back to Deque practice

LearningTree

LC 641 · Design Circular Deque — Solution & Explanation | DSA Guide