LeetCode 641 - Design Circular Deque

LeetCode Problem 641

Difficulty: 🟡 Medium
Topics: Array, Linked List, Design, Queue

Solution

Problem Understanding

The problem asks us to design a circular double-ended queue, also called a deque. A deque is a data structure that allows insertion and deletion from both the front and the rear. Unlike a normal queue, which only supports enqueue at the back and dequeue at the front, a deque supports operations at both ends efficiently.

The word "circular" is the key part of this problem. Instead of shifting elements when the structure reaches the end of the array, the indices wrap around to the beginning. This allows all operations to remain efficient without reallocating or moving elements.

We must implement a class with the following functionality:

• Insert at the front
• Insert at the rear
• Delete from the front
• Delete from the rear
• Retrieve the front value
• Retrieve the rear value
• Check whether the deque is empty
• Check whether the deque is full

The deque has a fixed capacity k, meaning it cannot grow dynamically. If the deque is already full, insertion operations must fail and return false. Similarly, if the deque is empty, deletion operations must fail and return false.

The constraints are small:

• 1 <= k <= 1000
• At most 2000 operations

Even though the constraints are not large, the problem is fundamentally a data structure design problem. The goal is not merely to pass the constraints, but to implement all operations efficiently.

A naive implementation could repeatedly shift elements inside an array when inserting or deleting from the front. That would work functionally, but it would make some operations linear time. The intended solution achieves constant time for every operation.

Several edge cases are important:

• Inserting into a full deque
• Deleting from an empty deque
• Correctly wrapping indices when they move past either end of the array
• Handling the case where the deque contains exactly one element
• Maintaining correct front and rear positions after many wraparounds

The problem guarantees that all method calls follow the required signatures, and values are always within the allowed range.

Approaches

Brute Force Approach

The most straightforward solution is to use a dynamic list or array and manually simulate deque behavior.

For example:

• insertFront could use list.insert(0, value)
• insertLast could use append
• deleteFront could use pop(0)
• deleteLast could use pop()

This approach is easy to implement and produces correct results because the list always maintains the correct order of elements.

However, operations at the front of a standard array-based list are expensive. Inserting or deleting at index 0 requires shifting every remaining element one position. That makes those operations O(n).

Even though the constraints are relatively small, this does not satisfy the intended design requirement of efficient deque operations.

Optimal Approach

The optimal solution uses a fixed-size circular array.

The key insight is that we do not need to physically move elements when inserting or deleting from either end. Instead, we maintain:

• A front pointer
• A rear pointer
• A size counter

The array acts like a ring. When an index moves past the end of the array, it wraps back to the beginning using modulo arithmetic.

For example:

(index + 1) % capacity

This circular behavior allows every operation to be completed in constant time.

The most important observation is that the logical order of the deque does not need to match the physical layout in memory. We only need correct pointer management.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per front operation	O(k)	Uses list shifting for front insertions and deletions
Optimal	O(1) per operation	O(k)	Uses circular array with modular arithmetic

Algorithm Walkthrough

1. Initialize a fixed-size array of length k.

This array stores all deque elements. Since the maximum size is fixed, we never need to resize it. 2. Maintain a front index.

The front index always points to the current front element of the deque. 3. Maintain a rear index.

The rear index always points to the position where the next rear insertion will occur. 4. Maintain a size variable.

This tracks the number of elements currently in the deque. It allows us to determine whether the deque is empty or full. 5. For insertFront, first check whether the deque is full.

If full, return False.

Otherwise:

• Move front backward by one position using circular arithmetic.
• Store the value at the new front position.
• Increment size.

6. For insertLast, first check whether the deque is full.

If full, return False.

Otherwise:

• Store the value at the current rear position.
• Move rear forward using circular arithmetic.
• Increment size.

7. For deleteFront, first check whether the deque is empty.

If empty, return False.

Otherwise:

• Move front forward by one position.
• Decrement size.

8. For deleteLast, first check whether the deque is empty.

If empty, return False.

Otherwise:

• Move rear backward by one position.
• Decrement size.

9. For getFront, return the element at the front index if the deque is not empty.
10. For getRear, return the element immediately before the rear pointer.

Since rear points to the next insertion position, the actual rear element is located at:

(rear - 1 + capacity) % capacity

1. isEmpty returns whether size == 0.
2. isFull returns whether size == capacity.

Why it works

The correctness comes from maintaining a consistent invariant:

• front always points to the first valid element
• rear always points to the next insertion position at the back
• size always equals the number of stored elements

Modulo arithmetic guarantees indices always remain within array bounds while still behaving like a circular structure. Since elements are never shifted, all operations remain constant time.

Python Solution

class MyCircularDeque:

    def __init__(self, k: int):
        self.capacity = k
        self.deque = [0] * k
        self.front = 0
        self.rear = 0
        self.size = 0

    def insertFront(self, value: int) -> bool:
        if self.isFull():
            return False

        self.front = (self.front - 1 + self.capacity) % self.capacity
        self.deque[self.front] = value
        self.size += 1

        return True

    def insertLast(self, value: int) -> bool:
        if self.isFull():
            return False

        self.deque[self.rear] = value
        self.rear = (self.rear + 1) % self.capacity
        self.size += 1

        return True

    def deleteFront(self) -> bool:
        if self.isEmpty():
            return False

        self.front = (self.front + 1) % self.capacity
        self.size -= 1

        return True

    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False

        self.rear = (self.rear - 1 + self.capacity) % self.capacity
        self.size -= 1

        return True

    def getFront(self) -> int:
        if self.isEmpty():
            return -1

        return self.deque[self.front]

    def getRear(self) -> int:
        if self.isEmpty():
            return -1

        rear_index = (self.rear - 1 + self.capacity) % self.capacity
        return self.deque[rear_index]

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == self.capacity

The implementation starts by allocating a fixed-size array and initializing tracking variables. The front and rear pointers both begin at index 0, while size starts at 0.

The insertion methods first verify that space exists. insertFront moves the front pointer backward before storing the new value, while insertLast stores the value first and then advances the rear pointer.

The deletion methods simply move pointers and decrease the size counter. No element shifting occurs, which is why operations remain constant time.

The retrieval methods rely on the pointer invariant. getFront directly accesses the front index, while getRear computes the previous index before rear.

Modulo arithmetic is essential throughout the implementation because it ensures indices wrap around correctly.

Go Solution

type MyCircularDeque struct {
	deque    []int
	front    int
	rear     int
	size     int
	capacity int
}

func Constructor(k int) MyCircularDeque {
	return MyCircularDeque{
		deque:    make([]int, k),
		front:    0,
		rear:     0,
		size:     0,
		capacity: k,
	}
}

func (this *MyCircularDeque) InsertFront(value int) bool {
	if this.IsFull() {
		return false
	}

	this.front = (this.front - 1 + this.capacity) % this.capacity
	this.deque[this.front] = value
	this.size++

	return true
}

func (this *MyCircularDeque) InsertLast(value int) bool {
	if this.IsFull() {
		return false
	}

	this.deque[this.rear] = value
	this.rear = (this.rear + 1) % this.capacity
	this.size++

	return true
}

func (this *MyCircularDeque) DeleteFront() bool {
	if this.IsEmpty() {
		return false
	}

	this.front = (this.front + 1) % this.capacity
	this.size--

	return true
}

func (this *MyCircularDeque) DeleteLast() bool {
	if this.IsEmpty() {
		return false
	}

	this.rear = (this.rear - 1 + this.capacity) % this.capacity
	this.size--

	return true
}

func (this *MyCircularDeque) GetFront() int {
	if this.IsEmpty() {
		return -1
	}

	return this.deque[this.front]
}

func (this *MyCircularDeque) GetRear() int {
	if this.IsEmpty() {
		return -1
	}

	rearIndex := (this.rear - 1 + this.capacity) % this.capacity
	return this.deque[rearIndex]
}

func (this *MyCircularDeque) IsEmpty() bool {
	return this.size == 0
}

func (this *MyCircularDeque) IsFull() bool {
	return this.size == this.capacity
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * obj := Constructor(k);
 * param_1 := obj.InsertFront(value);
 * param_2 := obj.InsertLast(value);
 * param_3 := obj.DeleteFront();
 * param_4 := obj.DeleteLast();
 * param_5 := obj.GetFront();
 * param_6 := obj.GetRear();
 * param_7 := obj.IsEmpty();
 * param_8 := obj.IsFull();
 */

The Go implementation closely mirrors the Python version. The primary difference is that Go requires explicit struct fields and method receivers.

The deque storage uses a slice with fixed length. Pointer arithmetic and modulo operations work the same way as in Python.

Because Go does not have dynamic resizing here, the implementation remains fully constant time for all operations.

Worked Examples

Example 1

Input:

["MyCircularDeque",
 "insertLast",
 "insertLast",
 "insertFront",
 "insertFront",
 "getRear",
 "isFull",
 "deleteLast",
 "insertFront",
 "getFront"]

Capacity:

k = 3

Step-by-step Trace

Operation	Result	Array State	Front	Rear	Size
Initialize	null	[0,0,0]	0	0	0
insertLast(1)	true	[1,0,0]	0	1	1
insertLast(2)	true	[1,2,0]	0	2	2
insertFront(3)	true	[1,2,3]	2	2	3
insertFront(4)	false	[1,2,3]	2	2	3
getRear()	2	[1,2,3]	2	2	3
isFull()	true	[1,2,3]	2	2	3
deleteLast()	true	[1,2,3]	2	1	2
insertFront(4)	true	[1,4,3]	1	1	3
getFront()	4	[1,4,3]	1	1	3

Logical Deque View

Even though the physical array looks like:

[1,4,3]

The logical deque order after the final step is:

[4,3,1]

This demonstrates why circular indexing is important. The logical order is determined by the front pointer, not by the raw array layout.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Every operation performs only constant-time pointer arithmetic
Space	O(k)	The deque stores at most k elements

The implementation never shifts elements or resizes the array. Every insertion, deletion, and retrieval operation modifies only a few indices and counters. Because the underlying array has fixed capacity k, the space complexity is linear in the deque size limit.

Test Cases

# Provided example
deque = MyCircularDeque(3)

assert deque.insertLast(1) is True       # insert rear
assert deque.insertLast(2) is True       # insert rear again
assert deque.insertFront(3) is True      # insert front
assert deque.insertFront(4) is False     # full deque
assert deque.getRear() == 2              # rear value
assert deque.isFull() is True            # deque should be full
assert deque.deleteLast() is True        # delete rear
assert deque.insertFront(4) is True      # insert front after delete
assert deque.getFront() == 4             # front value

# Single element capacity
deque = MyCircularDeque(1)

assert deque.isEmpty() is True           # initially empty
assert deque.insertLast(10) is True      # insert succeeds
assert deque.isFull() is True            # now full
assert deque.insertFront(20) is False    # cannot insert when full
assert deque.getFront() == 10            # front value
assert deque.getRear() == 10             # rear value
assert deque.deleteFront() is True       # remove only element
assert deque.isEmpty() is True           # empty again

# Delete from empty deque
deque = MyCircularDeque(2)

assert deque.deleteFront() is False      # cannot delete from empty
assert deque.deleteLast() is False       # cannot delete from empty
assert deque.getFront() == -1            # no front value
assert deque.getRear() == -1             # no rear value

# Wraparound behavior
deque = MyCircularDeque(3)

assert deque.insertLast(1) is True
assert deque.insertLast(2) is True
assert deque.insertLast(3) is True
assert deque.deleteFront() is True
assert deque.insertLast(4) is True       # wraps around

assert deque.getFront() == 2             # correct front after wrap
assert deque.getRear() == 4              # correct rear after wrap

# Multiple front operations
deque = MyCircularDeque(5)

assert deque.insertFront(1) is True
assert deque.insertFront(2) is True
assert deque.insertFront(3) is True

assert deque.getFront() == 3             # newest front
assert deque.getRear() == 1              # oldest rear

assert deque.deleteFront() is True
assert deque.getFront() == 2             # updated front

# Multiple rear deletions
deque = MyCircularDeque(4)

assert deque.insertLast(5) is True
assert deque.insertLast(6) is True
assert deque.insertLast(7) is True

assert deque.deleteLast() is True
assert deque.getRear() == 6              # rear updated correctly

assert deque.deleteLast() is True
assert deque.getRear() == 5              # only one left

assert deque.deleteLast() is True
assert deque.isEmpty() is True           # completely empty

Test	Why
Provided example	Validates overall correctness
Capacity 1 deque	Tests smallest allowed size
Delete from empty	Ensures proper failure handling
Wraparound behavior	Verifies circular indexing logic
Multiple front insertions	Tests front pointer updates
Multiple rear deletions	Tests rear pointer updates

Edge Cases

One important edge case occurs when inserting into a full deque. Without a proper size check, a new insertion could overwrite existing elements and corrupt the structure. The implementation prevents this by checking isFull() before every insertion operation.

Another critical edge case is deleting from an empty deque. Attempting to move pointers when no elements exist can easily produce invalid states or incorrect retrieval results. The implementation handles this safely by immediately returning False without modifying any internal state.

A particularly subtle case involves circular wraparound. For example, after repeated insertions and deletions, the front pointer may become larger than the rear pointer. A naive implementation might assume elements are always stored contiguously, which is incorrect in a circular buffer. Using modulo arithmetic guarantees indices remain valid and logically connected regardless of how many times they wrap around.

A final edge case occurs when the deque contains exactly one element. In that situation, both front and rear operations interact with the same logical position. Incorrect pointer updates can accidentally skip or duplicate elements. The implementation avoids this problem by relying on the size variable as the authoritative source of how many valid elements exist.