Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

The task is to build a fixed-capacity first-in, first-out queue. It must support inserting at the rear, deleting from the front, reading both ends, and checking whether it is empty or full. An attempted insertion into a full queue and an attempted deletion from an empty queue must fail cleanly.

The interesting constraint is that every operation should take constant time. Shifting an array after each deletion would make deQueue linear, so the unused space at the beginning of the array must be reused instead.

Deriving the circular-array design

Imagine the array bent into a ring: after the final slot comes slot zero again. The queue needs only four pieces of state:

  • a fixed array of capacity slots;
  • head, the index of the current front element;
  • size, the number of stored elements;
  • the invariant that logical element i lives at (head + i) % capacity.

That invariant makes every operation mechanical. The next insertion position is (head + size) % capacity. Deleting the front advances head by one position, also wrapping with modulo. The rear is the final logical element, at (head + size - 1) % capacity.

Tracking size removes the circular buffer’s only ambiguity. If head and the next insertion position are equal, the queue could be either empty or full; size == 0 and size == capacity distinguish those states directly. No element ever needs to move.

Why the design works

The invariant says the queue occupies size consecutive logical positions beginning at head, even when those positions cross the physical end of the array. Inserting writes immediately after that logical sequence and increases its length by one. Deleting advances past the first logical position and decreases the length by one. Both operations therefore preserve the invariant and FIFO order.

Because the implementation performs only index arithmetic and a constant number of reads or writes, every queue operation takes O(1) time. The fixed backing array uses O(k) space for capacity k.

Python solution

The class below uses the interface required by LeetCode. Its internal names document the representation, it validates construction, and deletion clears vacated slots so the same design would not retain object references if generalized beyond integers.

from __future__ import annotations


class MyCircularQueue:
    """A fixed-capacity FIFO queue backed by a circular array."""

    __slots__ = ("_capacity", "_slots", "_head", "_size")

    def __init__(self, k: int):
        """Create an empty queue that can hold exactly k integers."""
        if k <= 0:
            raise ValueError("Queue capacity must be positive")

        self._capacity = k
        self._slots: list[int | None] = [None] * k
        self._head = 0
        self._size = 0

    def _physical_index(self, logical_offset: int) -> int:
        """Map an offset from the logical front to its array index."""
        return (self._head + logical_offset) % self._capacity

    def enQueue(self, value: int) -> bool:
        """Insert value at the rear, returning False if the queue is full."""
        if self.isFull():
            return False

        insertion_index = self._physical_index(self._size)
        self._slots[insertion_index] = value
        self._size += 1
        return True

    def deQueue(self) -> bool:
        """Remove the front value, returning False if the queue is empty."""
        if self.isEmpty():
            return False

        # Clearing the slot prevents stale references in a generalized queue.
        self._slots[self._head] = None
        self._head = (self._head + 1) % self._capacity
        self._size -= 1
        return True

    def Front(self) -> int:
        """Return the front value, or -1 when the queue is empty."""
        if self.isEmpty():
            return -1

        value = self._slots[self._head]
        assert value is not None
        return value

    def Rear(self) -> int:
        """Return the rear value, or -1 when the queue is empty."""
        if self.isEmpty():
            return -1

        rear_index = self._physical_index(self._size - 1)
        value = self._slots[rear_index]
        assert value is not None
        return value

    def isEmpty(self) -> bool:
        """Return whether the queue contains no values."""
        return self._size == 0

    def isFull(self) -> bool:
        """Return whether the queue has reached its fixed capacity."""
        return self._size == self._capacity

Interview follow-ups

Can the queue work without storing size?

Yes. One common design stores separate head and tail indices and deliberately leaves one array slot unused. Then equal indices mean empty, while advancing the tail would make it equal to the head when the queue is full. The buffer must contain k + 1 physical slots to provide a logical capacity of k.

This still gives O(1) operations and O(k) space. The tradeoff is a slightly less direct representation: the allocated length no longer equals the advertised capacity. Another option is to keep all k slots and add a Boolean that records whether the most recent boundary-crossing operation made the queue full or empty, but a size counter is usually easier to reason about.

How would a linked-list implementation differ?

Maintain pointers to the front and rear nodes plus a size counter. Insertion links a new node after the rear; deletion moves the front pointer; when the final node is removed, both pointers become null. Comparing the size with k preserves the same fixed-capacity behavior.

All operations remain O(1), but the list allocates a node per element and pays for pointer storage and allocation overhead. The array version is normally faster and more cache-friendly when the maximum capacity is known, while a linked list is attractive when capacity should grow without copying.

How would the design support automatic growth?

When an insertion finds the buffer full, allocate a new array—commonly twice as large—and copy the size logical elements into indices 0 through size - 1 in queue order. Then set head to zero and insert into the enlarged array.

The resize itself costs O(k) time and temporarily needs O(k) additional space, but geometric growth makes insertion O(1) amortized across a long sequence of operations. It changes the contract from a fixed-capacity queue, so isFull either disappears or refers only to an external maximum limit.

How would the queue become thread-safe?

Protect every operation that reads or changes head, size, or the backing array with the same mutex. A single lock is sufficient because each public method is short, and it makes each operation appear atomic to other threads. Merely making the counter atomic would not work: an insertion must update both a slot and the size as one consistent action.

Locking preserves O(1) work per method but introduces contention. A blocking queue can add not_empty and not_full condition variables so consumers sleep when empty and producers sleep when full. A lock-free bounded queue is possible, but it requires atomic sequence numbers or careful memory-ordering rules and is substantially harder to prove correct.

How would the structure be extended into a circular deque?

Keep the same array, head index, and size. Inserting at the front first moves head one position backward with (head - 1) % capacity, then writes there. Deleting from the rear clears the slot at (head + size - 1) % capacity and decrements the size. The existing rear insertion and front deletion stay unchanged.

Every operation remains O(1) and space remains O(k). The main implementation tradeoff is a larger API and more boundary cases, so tests should deliberately exercise wraparound from both directions as well as transitions between empty, partially full, and full states.

What changes in a language where integer overflow is possible?

The expression head + size can overflow a fixed-width integer if indices are allowed to grow without bound. This implementation avoids that issue in practice because head and size are always below capacity, but a capacity near the integer limit could still make their sum overflow before modulo is applied.

Use overflow-safe conditional arithmetic—for example, compare the offset with capacity - head before adding—or choose an unsigned type whose maximum is known to exceed twice the largest legal capacity. These alternatives keep O(1) performance while making the index proof valid for the target language’s numeric model.

Which tests best expose circular-buffer bugs?

The most valuable sequence fills the queue, removes several front elements, and then inserts enough values to wrap the rear past the array’s end. At each step, verify Front, Rear, isEmpty, isFull, and the Boolean result of the attempted operation. Also test capacity one, repeated failed operations on empty and full queues, and several complete empty-to-full-to-empty cycles.

Those cases specifically cross representation boundaries that ordinary straight-line examples miss. They do not change the algorithm’s complexity, but they make off-by-one errors, stale rear calculations, and incorrect empty/full disambiguation much easier to detect.

Takeaway

A circular queue becomes simple once its invariant is explicit: logical element i is stored at (head + i) % capacity. With head identifying the front and size distinguishing empty from full, insertion and deletion only change one slot and a few integers. The array never shifts, so all required operations stay constant-time.