Abstract / Summary

Design a data structure that supports adding and removing elements from both the front and back efficiently.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 65% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Design
• Linked List
• Queue

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The class implements a fixed-size circular double-ended queue (deque) using a plain Python list as the underlying storage. Two integer indices, front and back, delimit the active region: front points at the current first element, while back points one position past the last element. A size counter tracks the number of valid entries, and capacity stores the maximum number of elements the deque can hold. All operations run in constant time because they manipulate only indices and a single array slot.

Core Operations

Construction

def __init__(self, k: int):
    self.front = 0          # points at first entry
    self.back  = 0          # points beyond last entry
    self.data  = [0] * k    # pre-allocated storage
    self.size  = 0
    self.capacity = k

The constructor pre-allocates a list of length k. By fixing the storage up front, the implementation avoids dynamic resizing during normal operation, which eliminates allocation overhead and keeps memory layout stable.

Inserting at the Front

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

    self.front -= 1
    if self.front < 0:
        self.front += self.capacity

    self.data[self.front] = value
    self.size += 1
    return True

The method first checks for a full deque. If space exists, it decrements front and wraps it around when it becomes negative, thereby moving the logical front pointer backward in the circular buffer. The new value is written directly into the computed slot, and the element count is increased.

Inserting at the Rear

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

    self.data[self.back] = value
    self.size += 1

    self.back += 1
    if self.back == self.capacity:
        self.back = 0

    return True

After confirming capacity, the value is stored at the current back index. The back pointer is then advanced, wrapping to zero when it reaches the end of the underlying array. This mirrors the front insertion logic but moves in the opposite direction.

Deleting from the Front

def deleteFront(self) -> bool:
    if self.size == 0:
        return False

    self.front += 1
    if self.front == self.capacity:
        self.front = 0

    self.size -= 1
    return True

When the deque is non-empty, the method advances front past the current first element, wrapping to zero if necessary, and decrements the size counter. The actual data slot is left untouched; it will be overwritten on a subsequent insertion.

Deleting from the Rear

def deleteLast(self) -> bool:
    if self.size == 0:
        return False

    self.back -= 1
    if self.back < 0:
        self.back += self.capacity

    self.size -= 1
    return True

The rear pointer is moved backward, with wrap-around handling for negative indices, and the size is reduced. As with deleteFront, the content of the vacated slot remains unchanged until overwritten.

Accessing the Front Element

def getFront(self) -> int:
    return self.data[self.front] if not self.isEmpty() else -1

If the deque contains elements, the value at the front index is returned; otherwise, a sentinel -1 signals emptiness.

Accessing the Rear Element

def getRear(self) -> int:
    if self.isEmpty():
        return -1
    pos = self.back - 1
    if pos < 0:
        pos += self.capacity
    return self.data[pos]

The method computes the logical last position by subtracting one from back and correcting for wrap-around. It then returns the stored value or -1 when the deque is empty.

Emptiness and Fullness Checks

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

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

Both predicates rely on the size counter, providing O(1) answers without inspecting the underlying array.

Edge Cases Handled

The implementation explicitly guards against overflow and underflow. Insertion methods reject operations when size equals capacity, preventing overwriting existing data. Deletion methods reject operations when size is zero, avoiding moving pointers into an invalid region. Wrap-around logic in each pointer adjustment ensures that indices remain within [0, capacity-1] even when they cross the array boundaries. The getRear method includes a separate wrap-around step because back points one slot beyond the last element, requiring a correction before indexing.

Performance Optimizations

All mutating operations modify only a handful of integer variables and a single array slot, guaranteeing constant-time execution. Pre-allocating the storage array eliminates the need for dynamic list growth, which would otherwise introduce occasional O(n) reallocations. The use of a size field avoids recomputing the element count from the two pointers, allowing immediate answers for isEmpty and isFull. Index adjustments employ simple arithmetic with conditional branches rather than modulo operations, which can be marginally faster on typical CPUs because the branch is taken only when crossing the boundary. The design also avoids any auxiliary data structures, keeping the memory footprint minimal and cache-friendly.

Imagine a magical train that goes around in a perfect circle. This train has a set number of small carts that can hold one toy each.

At the very beginning, the train is empty. A special conductor keeps track of two important spots. The front spot is where the train begins, and the back spot is where the train finishes adding new toys.

When a new toy needs to join at the front, the train shifts to make room just before the current front spot. If the front spot reaches the very start of the circle, it wraps around to the back to find space again.

When a new toy joins at the back, it sits in the spot where the conductor is waiting. After the toy is inside, the conductor moves to the next spot to be ready for the next toy. Just like with the front, if the conductor moves past the end of the train, they hop back around to the beginning.

If there are too many toys and no empty carts left, the train knows it is full and cannot take any more. If there are no toys to take away, the train knows it is empty.

Taking a toy out of the front or the back is just the opposite. The train remembers which cart has a toy, removes it, and updates which cart comes next in the circle. Because the track is a circle, the front and back spots are always sliding along, always making sure there is room for toys to get on or off.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: constant
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python							TS
	WalkCCC	C++	Java
	leetcode.ca	C++	Java	Python						Go	TS
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	black-shadows	C++
	charles-wangkai		Java
	DimitrisJim								C
	everthis				JS
	fartem						Ruby
	FelixFan1122		Java
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007			Python
	ruoru					Rust
	suxrobGM							C#
	varunu28		Java
	withaarzoo	C++
	YuriSpiridonov			Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
FelixFan1122	Java
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
ruoru	Rust
suxrobGM	C#
varunu28	Java
withaarzoo	C++
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality