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.

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

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

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

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