622. Design Circular Queue

At a Glance

Topic: system-design-coding
Pattern: Array + front/rear pointers
Difficulty: Medium
Companies: Amazon, Microsoft, Bloomberg, Cisco, Oracle
Frequency: Medium
LeetCode: 622

Problem (one-liner)

Implement a fixed-capacity circular queue using an array: enQueue, deQueue, Front, Rear, isEmpty, isFull in O(1).

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

Fixed capacity with reuse of slots — modulo indexing
Track size or leave one slot empty to distinguish full vs empty

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 — slice length capacity, frontIndex, length counter — clean full/empty tests.

Optimal Solution

Go

package main

// MyCircularQueue API:
// - Constructor(k int)
// - bool enQueue(value int)
// - bool deQueue()
// - int Front()
// - int Rear()
// - bool isEmpty()
// - bool isFull()

type MyCircularQueue struct {
	buffer     []int
	frontIndex int
	length     int
	capacity   int
}

func Constructor(k int) MyCircularQueue {
	return MyCircularQueue{
		buffer:   make([]int, k),
		capacity: k,
	}
}

func (queue *MyCircularQueue) EnQueue(value int) bool {
	if queue.IsFull() {
		return false
	}
	rearIndex := (queue.frontIndex + queue.length) % queue.capacity
	queue.buffer[rearIndex] = value
	queue.length++
	return true
}

func (queue *MyCircularQueue) DeQueue() bool {
	if queue.IsEmpty() {
		return false
	}
	queue.frontIndex = (queue.frontIndex + 1) % queue.capacity
	queue.length--
	return true
}

func (queue *MyCircularQueue) Front() int {
	if queue.IsEmpty() {
		return -1
	}
	return queue.buffer[queue.frontIndex]
}

func (queue *MyCircularQueue) Rear() int {
	if queue.IsEmpty() {
		return -1
	}
	rearIndex := (queue.frontIndex + queue.length - 1) % queue.capacity
	return queue.buffer[rearIndex]
}

func (queue *MyCircularQueue) IsEmpty() bool {
	return queue.length == 0
}

func (queue *MyCircularQueue) IsFull() bool {
	return queue.length == queue.capacity
}

JavaScript

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

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

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

	front() {
		if (this.isEmpty()) {
			return -1;
		}
		return this.buffer[this.frontIndex];
	}

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

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

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

Walkthrough

Capacity 3: enqueue 1,2,3 fills; front at index 0, rear at index 2. Dequeue advances frontIndex, freeing a slot at the logical front.

Invariant: length elements occupy consecutive slots modulo capacity starting at frontIndex.

Edge Cases

Single-slot queue
Full queue rejects enqueue

Pitfalls

Computing rearIndex with (front + length - 1) mod k when empty guard missed
Confusing sentinel wasted slot vs size tracking — pick one approach consistently

Variants

Lock-free ring buffer (systems).
Resizeable deque amortized.

Mind-Map Tags

#circular-buffer #modulo-index #fixed-capacity #queue #array