Design Circular Queue (LC 622)

Pattern: Queue — ring buffer design
Difficulty: Medium
Key Concept: Wrap indices with % capacity to reuse freed slots. Track an explicit count so “full” and “empty” are never ambiguous.

Problem Statement

Design a circular queue (ring buffer) of fixed capacity k supporting:

Method	Contract
`MyCircularQueue(k)`	create with capacity `k`
`enQueue(int value)`	insert at the rear; `false` if full
`deQueue()`	delete from the front; `false` if empty
`Front()`	front element, or `-1` if empty
`Rear()`	rear element, or `-1` if empty
`isEmpty()` / `isFull()`	state checks

All operations must be O(1).

1. Algorithm & Pseudocode

Naive (shift on dequeue)

deQueue(): remove buf[0], then shift every remaining element one slot left   // O(n)

Optimal (ring buffer)

buf[]  = new int[k]
head   = 0        // index of the front element
count  = 0        // how many elements are live  ← store this, NOT a tail pointer

enQueue(v):
    if count == k: return false
    buf[(head + count) % k] = v        // rear index is DERIVED from head + count
    count++
    return true

deQueue():
    if count == 0: return false
    head = (head + 1) % k              // just move the window; no shifting, no clearing
    count--
    return true

Front(): count == 0 ? -1 : buf[head]
Rear():  count == 0 ? -1 : buf[(head + count - 1) % k]
isEmpty(): count == 0
isFull():  count == k

2. Step-by-Step Analysis (Beginner-Friendly)

Why a plain array queue is broken With a plain array, dequeuing from the front means shifting everything left — O(n) per dequeue. Alternatively you advance a head pointer and never reuse the freed slots, so the array “walks off the end” and you run out of space even when the queue is nearly empty.
The circular fix Let the indices wrap: after index k-1 comes index 0 again. (i + 1) % k does this in one operation. The queue becomes a window sliding around a fixed ring — nothing is ever moved, only the window’s start and length change.
The classic ambiguity — and how count kills it With head and tail pointers, head == tail means both “empty” and “full”. You can’t distinguish them. Three standard fixes:
- Store count (used here) — simplest, uses all k slots, and every method reads naturally.
- Waste one slot — “full” becomes (tail + 1) % k == head; you only ever store k-1.
- Store a boolean isFull flag — works, but is one more piece of state to keep in sync.
Whichever you pick, name the ambiguity out loud — it is the entire point of the question.
Why derive the rear instead of storing it rear = (head + count - 1) % k is always consistent by construction. A separately stored tail is a second source of truth that can drift out of sync with head and count — one more invariant to maintain and one more place to have a bug.
You never clear removed slots deQueue just moves head and decrements count. The stale value stays in the array but is outside the live window, so it’s unreachable — and it’ll be overwritten by the next enQueue. (In a generic Queue<T> you would null out the slot, to release the reference for GC. Worth mentioning.)

3. The Dry Run

MyCircularQueue(3) — buf = [_, _, _], head = 0, count = 0

Call	Computation	`buf`	head	count	Returns
`enQueue(1)`	`buf[(0+0)%3] = 1`	`[1,_,_]`	0	1	true
`enQueue(2)`	`buf[(0+1)%3] = 2`	`[1,2,_]`	0	2	true
`enQueue(3)`	`buf[(0+2)%3] = 3`	`[1,2,3]`	0	3	true
`enQueue(4)`	`count == 3 == k`	`[1,2,3]`	0	3	false (full)
`Rear()`	`buf[(0+3-1)%3] = buf[2]`	`[1,2,3]`	0	3	3
`isFull()`	`3 == 3`		0	3	true
`deQueue()`	`head = (0+1)%3 = 1`	`[1,2,3]`	1	2	true
`enQueue(4)`	`buf[(1+2)%3] = buf[0] = 4`	`[4,2,3]`	1	3	true
`Rear()`	`buf[(1+3-1)%3] = buf[0]`	`[4,2,3]`	1	3	4
`Front()`	`buf[1]`	`[4,2,3]`	1	3	2

Note step 8: index 0 — freed by the dequeue — got reused by the wrap. That’s the ring.

Visual

      after enQueue(4), head=1, count=3

         idx:   0     1     2
              ┌─────┬─────┬─────┐
        buf = │  4  │  2  │  3  │
              └─────┴─────┴─────┘
                 ▲     ▲
               rear   head          window = head → head+count-1, wrapping at k

        live order (FIFO): 2, 3, 4

4. Java Solution

Naive (O(n) dequeue)

class MyCircularQueueSlow {
    private final int[] buf; private int size = 0;
    MyCircularQueueSlow(int k) { buf = new int[k]; }

    boolean enQueue(int v) {
        if (size == buf.length) return false;
        buf[size++] = v; return true;
    }
    boolean deQueue() {
        if (size == 0) return false;
        System.arraycopy(buf, 1, buf, 0, --size);   // shift everything left — O(n)
        return true;
    }
}

deQueue O(n) — fails the O(1) requirement

Optimal (ring buffer)

class MyCircularQueue {
    private final int[] buf;
    private int head = 0;    // index of the front element
    private int count = 0;   // number of live elements — resolves the full/empty ambiguity

    public MyCircularQueue(int k) {
        buf = new int[k];
    }

    public boolean enQueue(int value) {
        if (isFull()) return false;
        buf[(head + count) % buf.length] = value;   // rear is DERIVED, never stored
        count++;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % buf.length;             // slide the window; nothing is moved
        count--;
        return true;
    }

    public int Front() {
        return isEmpty() ? -1 : buf[head];
    }

    public int Rear() {
        return isEmpty() ? -1 : buf[(head + count - 1) % buf.length];
    }

    public boolean isEmpty() { return count == 0; }
    public boolean isFull()  { return count == buf.length; }
}

All operations O(1) · Space O(k), allocated once up front

5. The “Java vs. Others” Edge

int[] over ArrayList<Integer> — fixed capacity is a requirement here, so the dynamic growth of ArrayList is pure overhead, and it boxes every element. A primitive array is exactly one contiguous allocation with zero indirection.
% buf.length vs bit masking — if you round the capacity up to a power of two you can replace % n with & (n - 1), which is meaningfully faster (integer division is one of the slowest ALU ops). That’s how ArrayDeque and Disruptor-style ring buffers do it internally. Worth naming as an optimisation; don’t complicate the interview answer with it unasked.
Beware % with negative operands — Java’s % returns a negative result for negative left operands (-1 % 3 == -1, not 2). It’s safe here because head + count is always ≥ 0, but if you ever decrement an index, use ((i - 1) % n + n) % n.
final int[] buf — capacity never changes, so final documents the invariant and lets the JIT hoist the bounds check.
This is ArrayDeque internally. java.util.ArrayDeque is a power-of-two circular array with head/tail cursors — which is exactly why it’s the right choice everywhere else in this pattern folder. Saying so connects the design question to real JDK code.
Generic version: for MyCircularQueue<T> you’d hold Object[] and null out the slot in deQueue so the dequeued object can be garbage collected. With int[] there’s no reference to release, so leaving the stale value is harmless.

6. Complexity Summary

Operation	Naive (shift)	Ring buffer
`enQueue`	O(1)	O(1)
`deQueue`	O(n)	O(1)
`Front` / `Rear`	O(1)	O(1)
`isEmpty` / `isFull`	O(1)	O(1)
Space	O(k)	O(k), allocated once

7. Edge Cases & Follow-Ups

k = 1 — head never moves off 0; Front() == Rear() whenever non-empty.
Wrap-around correctness — the test that catches most bugs: fill, dequeue a few, enqueue more so the window straddles the end of the array, then check Rear().
Empty accessors must return -1, not throw. Check isEmpty() first.
Follow-up: LC 641 Design Circular Deque — add insertFront (head = (head - 1 + k) % k) and deleteLast (just count--). Same buffer, two more methods.
Follow-up: make it thread-safe — either synchronized on every method, or a lock-free single-producer/single-consumer ring using AtomicInteger cursors. Real-world use: log buffers, audio/video frame buffers, LMAX Disruptor.
Follow-up: overwrite instead of reject when full — change enQueue to advance head as well when isFull(). That gives you a fixed-size “most recent N” buffer.

#	Problem	Difficulty	Connection
LC 641	Design Circular Deque	Medium	same ring, both ends
LC 232	Implement Queue using Stacks	Easy	queue from a different primitive
LC 346	Moving Average from Data Stream	Easy	fixed-size ring + running sum
LC 933	Number of Recent Calls	Easy	queue as a sliding-window log
LC 362	Design Hit Counter	Medium	ring of 300 second-buckets
LC 146	LRU Cache	Medium	HashMap + doubly-linked list (the next design step up)