641. Design Circular Deque

At a Glance

Topic: system-design-coding
Pattern: Array + front/rear pointers
Difficulty: Medium
Companies: Amazon, Google, Microsoft, Oracle, Adobe
Frequency: Medium
LeetCode: 641

Problem (one-liner)

Design a fixed-size double-ended queue: insert/delete at front and last, query ends, empty/full checks.

Recognition Cues

Same ring buffer as circular queue but advance either side with modulo

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Optimal — array with frontIndex pointing one slot before first element (or track size + rear) — symmetric insert/remove.

Optimal Solution

Go

package main

// MyCircularDeque API:
// - Constructor(k int)
// - bool insertFront(int value)
// - bool insertLast(int value)
// - bool deleteFront()
// - bool deleteLast()
// - int getFront()
// - int getRear()
// - bool isEmpty()
// - bool isFull()

type MyCircularDeque struct {
	data       []int
	frontIndex int
	length     int
	capacity   int
}

func Constructor(k int) MyCircularDeque {
	return MyCircularDeque{
		data:       make([]int, k),
		frontIndex: 0,
		length:     0,
		capacity:   k,
	}
}

func (deque *MyCircularDeque) InsertFront(value int) bool {
	if deque.IsFull() {
		return false
	}
	deque.frontIndex = (deque.frontIndex - 1 + deque.capacity) % deque.capacity
	deque.data[deque.frontIndex] = value
	deque.length++
	return true
}

func (deque *MyCircularDeque) InsertLast(value int) bool {
	if deque.IsFull() {
		return false
	}
	rearIndex := (deque.frontIndex + deque.length) % deque.capacity
	deque.data[rearIndex] = value
	deque.length++
	return true
}

func (deque *MyCircularDeque) DeleteFront() bool {
	if deque.IsEmpty() {
		return false
	}
	deque.frontIndex = (deque.frontIndex + 1) % deque.capacity
	deque.length--
	return true
}

func (deque *MyCircularDeque) DeleteLast() bool {
	if deque.IsEmpty() {
		return false
	}
	deque.length--
	return true
}

func (deque *MyCircularDeque) GetFront() int {
	if deque.IsEmpty() {
		return -1
	}
	return deque.data[deque.frontIndex]
}

func (deque *MyCircularDeque) GetRear() int {
	if deque.IsEmpty() {
		return -1
	}
	rearIndex := (deque.frontIndex + deque.length - 1 + deque.capacity) % deque.capacity
	return deque.data[rearIndex]
}

func (deque *MyCircularDeque) IsEmpty() bool {
	return deque.length == 0
}

func (deque *MyCircularDeque) IsFull() bool {
	return deque.length == deque.capacity
}

JavaScript

class MyCircularDeque {
	constructor(capacity) {
		this.data = new Array(capacity);
		this.frontIndex = 0;
		this.length = 0;
		this.capacity = capacity;
	}

	insertFront(value) {
		if (this.isFull()) {
			return false;
		}
		this.frontIndex = (this.frontIndex - 1 + this.capacity) % this.capacity;
		this.data[this.frontIndex] = value;
		this.length++;
		return true;
	}

	insertLast(value) {
		if (this.isFull()) {
			return false;
		}
		const rearIndex = (this.frontIndex + this.length) % this.capacity;
		this.data[rearIndex] = value;
		this.length++;
		return true;
	}

	deleteFront() {
		if (this.isEmpty()) {
			return false;
		}
		this.frontIndex = (this.frontIndex + 1) % this.capacity;
		this.length--;
		return true;
	}

	deleteLast() {
		if (this.isEmpty()) {
			return false;
		}
		this.length--;
		return true;
	}

	getFront() {
		if (this.isEmpty()) {
			return -1;
		}
		return this.data[this.frontIndex];
	}

	getRear() {
		if (this.isEmpty()) {
			return -1;
		}
		const rearIndex = (this.frontIndex + this.length - 1 + this.capacity) % this.capacity;
		return this.data[rearIndex];
	}

	isEmpty() {
		return this.length === 0;
	}

	isFull() {
		return this.length === this.capacity;
	}
}

Walkthrough

insertFront moves frontIndex backward (with wrap); insertLast mirrors circular queue rear placement. Deletes shrink from respective ends without shifting internal elements.

Invariant: occupied region is contiguous in the ring of length length anchored at frontIndex.

Edge Cases

Capacity 1 alternates push/pop sides
Wraparound across index 0

Pitfalls

InsertFront vs queue-only logic — must decrement front before write
Off-by-one on rearIndex when length drops to zero

Variants

Growable deque using doubling arrays.
Monotonic deque for sliding window problems.

Mind-Map Tags

#deque #ring-buffer #two-ended #array #modulo