#641 Design Circular Deque

frequently reported atAmazon

the problem

In plain words

Implement a fixed-capacity double-ended queue MyCircularDeque(k): insertFront, insertLast, deleteFront, deleteLast (return true/false), getFront, getRear (−1 if empty), isEmpty, isFull.

in k = 3; insertLast(1), insertLast(2), insertFront(3), insertFront(4), getRear(), isFull(), deleteLast(), insertFront(4), getFront()

out true, true, true, false, 2, true, true, true, 4

1 ≤ k ≤ 1000
0 ≤ value ≤ 1000
At most 2000 calls

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternStack & queue design

Same ring buffer as LC 622, plus moving head left: head = (head − 1 + k) % k. The + k keeps the index non-negative because Java's % can return negatives.

solutions

From brute force to optimal

Insert/remove at index 0 for the front, at the end for the back.

insertFront: add(0, v).
deleteFront: remove(0).
Back operations at the end of the list.

timefront ops O(n), back ops O(1)

Index-0 inserts/removes shift every element.

spaceO(k)

At most k elements.

javajava.util.*

1// On LeetCode, name this class MyCircularDeque.2class MyCircularDequeList {3    private final List<Integer> items = new ArrayList<>();4    private final int capacity;5 6    public MyCircularDequeList(int k) {7        capacity = k;8    }9 10    public boolean insertFront(int value) {11        if (isFull()) return false;12        items.add(0, value); // shifts everything right: O(n)13        return true;14    }15 16    public boolean insertLast(int value) {17        if (isFull()) return false;18        items.add(value);19        return true;20    }21 22    public boolean deleteFront() {23        if (isEmpty()) return false;24        items.remove(0); // shifts everything left: O(n)25        return true;26    }27 28    public boolean deleteLast() {29        if (isEmpty()) return false;30        items.remove(items.size() - 1);31        return true;32    }33 34    public int getFront() {35        return isEmpty() ? -1 : items.get(0);36    }37 38    public int getRear() {39        return isEmpty() ? -1 : items.get(items.size() - 1);40    }41 42    public boolean isEmpty() {43        return items.isEmpty();44    }45 46    public boolean isFull() {47        return items.size() == capacity;48    }49}

Ring buffer where head can step both ways; the rear is derived from head + size.

insertFront: head = (head − 1 + k) % k, write, size++.
insertLast: write at (head + size) % k, size++.
deleteFront: head = (head + 1) % k, size--. deleteLast: size--.

timeO(1) for every operation

Constant index arithmetic, no shifting.

spaceO(k)

One fixed array.

javajava.util.*

1class MyCircularDeque {2    private final int[] data;3    private int head = 0; // index of the front element4    private int size = 0;5 6    public MyCircularDeque(int k) {7        data = new int[k];8    }9 10    public boolean insertFront(int value) {11        if (isFull()) return false;12        head = (head - 1 + data.length) % data.length; // step left; +length avoids a negative index13        data[head] = value;14        size++;15        return true;16    }17 18    public boolean insertLast(int value) {19        if (isFull()) return false;20        data[(head + size) % data.length] = value;21        size++;22        return true;23    }24 25    public boolean deleteFront() {26        if (isEmpty()) return false;27        head = (head + 1) % data.length;28        size--;29        return true;30    }31 32    public boolean deleteLast() {33        if (isEmpty()) return false;34        size--; // the rear is defined by head + size, so shrinking size is enough35        return true;36    }37 38    public int getFront() {39        return isEmpty() ? -1 : data[head];40    }41 42    public int getRear() {43        return isEmpty() ? -1 : data[(head + size - 1) % data.length];44    }45 46    public boolean isEmpty() {47        return size == 0;48    }49 50    public boolean isFull() {51        return size == data.length;52    }53}

Let the library do the ring buffer; only enforce the capacity.

Reject inserts when size == k.
Delegate to offerFirst/offerLast/pollFirst/pollLast/peekFirst/peekLast.

timeO(1) amortized

ArrayDeque end operations are amortized O(1).

spaceO(k)

At most k stored elements.

javajava.util.*

1// On LeetCode, name this class MyCircularDeque.2class MyCircularDequeLibrary {3    private final Deque<Integer> dq = new ArrayDeque<>();4    private final int capacity;5 6    public MyCircularDequeLibrary(int k) {7        capacity = k;8    }9 10    public boolean insertFront(int value) {11        return !isFull() && dq.offerFirst(value);12    }13 14    public boolean insertLast(int value) {15        return !isFull() && dq.offerLast(value);16    }17 18    public boolean deleteFront() {19        return dq.pollFirst() != null;20    }21 22    public boolean deleteLast() {23        return dq.pollLast() != null;24    }25 26    public int getFront() {27        return dq.isEmpty() ? -1 : dq.peekFirst();28    }29 30    public int getRear() {31        return dq.isEmpty() ? -1 : dq.peekLast();32    }33 34    public boolean isEmpty() {35        return dq.isEmpty();36    }37 38    public boolean isFull() {39        return dq.size() == capacity;40    }41}

in the room

How to say it in the interview

talk track

Interviewers want the raw ring buffer; mention the ArrayDeque wrapper to show you know the library, then implement it by hand.

traps

(head − 1) % k is −1 when head is 0 in Java.

what they ask next

Follow-ups

Why keep size instead of only head and tail?

With just two indices, a full deque and an empty one both have head == tail. A size counter (or one wasted slot) tells them apart.

Make it grow instead of rejecting inserts when full?

Allocate an array twice as big and copy the elements in order, starting from head, so the new head is 0. Each insert is then amortized O(1) — this is what ArrayDeque does.

before you submit

Edge cases to test

insertFront on an empty deque with head = 0: head must wrap to k − 1, never −1.
k = 1: front and rear are the same slot.
getFront and getRear on an empty deque return −1.

practise next