641. Design Circular Deque

641

MediumData Structure DesignCircular array (fixed-capacity double-ended queue)Ring buffer with head pointer and count

Design Circular Deque

Design a double-ended queue of fixed capacity k. Support insertFront, insertLast, deleteFront, deleteLast (each returns whether it succeeded), plus getFront and getRear (return the boundary values or -1 when empty), and isEmpty / isFull queries. Insertions fail when full and deletions fail when empty.

Open official problem prompt ↗

In plain English

Build a deque whose front and back both accept and release elements in constant time, without ever reallocating or shifting the underlying storage.

Picture it like this

Think of a circular carousel of k seats. Instead of dragging passengers to seat 0, you just move a marker for where the front is; when it runs off the end it loops back to the first seat.

Example

Input: MyCircularDeque(3); insertLast(1); insertLast(2); insertFront(3); insertFront(4); getRear(); isFull(); deleteLast(); insertFront(4); getFront()
Output: [null, true, true, true, false, 2, true, true, true, 4]
Why: After 1,2 at the back and 3 at the front the deque holds [3,1,2] and is full, so insertFront(4) fails; getRear is 2; deleteLast drops 2 leaving room, insertFront(4) makes [4,3,1] and getFront is 4.

Constraints

1 <= k <= 10000 <= value <= 1000At most 2000 calls total across all methods

Pattern lesson

See the pattern, then code

Ring buffer with head pointer and count

↗

Data Structure Design

An API whose operations must meet strict O(1) or O(log n) contracts.. Store elements in a size-k array and track only a head index plus a live count. Front sits at head; rear sits at head+count-1, all taken modulo k, so nothing ever has to move.

New words, made simpleKnow these before the algorithm

Circular / ring buffer: A fixed array where index arithmetic is done modulo the length so the end wraps to the start.
Head pointer: The index of the current front element.
Deque: Double-ended queue; insert and remove at both ends.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Python list with insert(0)/pop(0)

Front operations shift every element, defeating the O(1) requirement.

Use a dynamic list and insert or delete at index 0 for the front.

Time O(k) per front operationSpace O(k)

Best choiceCircular array with head + size

Constant time at both ends with no shifting or resizing.

Fixed array, wrap indices modulo k, track head and a live count.

Time O(1) per operationSpace O(k)

The rule we keep true

Invariant

The live elements always occupy the k-length slots head, head+1, ..., head+size-1 (all taken modulo k), and size is exactly the number of live elements.

Why this is correct

Reasoning

Because capacity is fixed at k, an element's logical position maps to a physical slot by a single modulo. Moving head or changing size relabels the window of live slots without touching data, so every boundary operation is arithmetic only.

The algorithm in three movesSay these aloud before coding

1Allocate a fixed array of size k and keep head=0, size=0

insertLast(1),insertLast(2) -> head=0 size=2 buf=[1,2,_]

2insertFront moves head back one slot (mod k); insertLast writes at (head+size) mod k

insertFront(3) -> head=2 size=3 buf=[1,2,3]

3Each successful insert/delete adjusts size and returns whether capacity/emptiness allowed it

insertFront(4) -> size==cap, return False

4getFront reads buf[head]; getRear reads buf[(head+size-1) mod k]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readvalues 1 then 2

2 · AskIs there room at the back?

3 · Update statehead=0, size=2, buf=[1,2,_]

4 · Resultboth succeed, return true

Key takeaway

A three-slot ring buffer; head wraps backward on insertFront and the rear index is computed as (head+size-1) mod k.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 2-6Fixed storage and cursors
buf never resizes; head marks the front and size counts live elements.
2
Lines 8-14insertFront
Move head one slot backward with modulo, then write, so the new element becomes the front.
3
Lines 16-21insertLast
Write at (head+size) mod k, the slot just past the current rear.
4
Lines 38-41getRear
Compute (head+size-1) mod k to find the last live slot without storing a separate tail.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

k=1 (a single slot acts as both front and rear)
Every operation on an empty deque returns -1 or false
Filling to capacity then inserting must fail, not overwrite
Deleting the last element then inserting reuses freed slots correctly

Common beginner mistakes

Using (head-1) without % k, producing a negative Python index that silently wraps wrong when combined with size math
Confusing capacity with current size when checking full/empty
Storing a separate tail pointer and letting it drift out of sync with head+size

Check your understanding

Why is a plain Python list with insert(0, x) unacceptable here?

PyPython 3 · solution.py

Optimal

1class MyCircularDeque:2    def __init__(self, k: int):3        self.cap = k4        self.buf = [0] * k5        self.head = 06        self.size = 078    def insertFront(self, value: int) -> bool:9        if self.size == self.cap:10            return False11        self.head = (self.head - 1) % self.cap12        self.buf[self.head] = value13        self.size += 114        return True1516    def insertLast(self, value: int) -> bool:17        if self.size == self.cap:18            return False19        self.buf[(self.head + self.size) % self.cap] = value20        self.size += 121        return True2223    def deleteFront(self) -> bool:24        if self.size == 0:25            return False26        self.head = (self.head + 1) % self.cap27        self.size -= 128        return True2930    def deleteLast(self) -> bool:31        if self.size == 0:32            return False33        self.size -= 134        return True3536    def getFront(self) -> int:37        return -1 if self.size == 0 else self.buf[self.head]3839    def getRear(self) -> int:40        return -1 if self.size == 0 else self.buf[(self.head + self.size - 1) % self.cap]4142    def isEmpty(self) -> bool:43        return self.size == 04445    def isFull(self) -> bool:46        return self.size == self.cap

Time complexityO(1) per operationOptimized

Space complexityO(k)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleMicrosoft

Design Circular Deque

Design Circular Deque

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Data Structure Design