Design Circular Deque

Medium
2055.

Design Circular Deque

Design Circular Deque is a medium coding problem on arrays and queue, asked in Amazon, Google and Microsoft interviews.

Implement a circular double-ended queue of fixed capacity, where elements can be added and removed at both ends, without using a built-in deque. Write the class MyCircularDeque:

  • MyCircularDeque(int k) creates a deque that holds at most k elements.
  • boolean insertFront(int value) / boolean insertLast(int value) add value at the front / back; they return true on success and false if the deque is full.
  • boolean deleteFront() / boolean deleteLast() remove the front / back element; they return true on success and false if the deque is empty.
  • int getFront() / int getRear() return the front / back element, or -1 if the deque is empty.
  • boolean isEmpty() / boolean isFull() report whether the deque is empty / full.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

Example 1

Input
["MyCircularDeque","insertLast","insertLast","insertFront","insertFront","getRear","isFull","deleteLast","insertFront","getFront"] [[3],[1],[2],[3],[4],[],[],[],[4],[]]
Output
[null,true,true,true,false,2,true,true,true,4]
Explanation
Capacity 3 holds [3,1,2]; inserting 4 at the front fails. The rear is 2. After deleteLast the deque is [3,1], so 4 fits at the front and becomes getFront.

Example 2

Input
["MyCircularDeque","getFront","deleteLast","insertFront","insertLast","getRear","deleteFront","getFront","isEmpty"] [[2],[],[],[5],[8],[],[],[],[]]
Output
[null,-1,false,true,true,8,true,8,false]
Explanation
An empty deque answers -1 and refuses to delete. After [5,8], the rear is 8; deleting the front leaves 8 at both ends.

Constraints

  • 1 <= k <= 1000
  • 0 <= value <= 1000
  • At most 2000 calls are made to insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty and isFull
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} k
 */
var MyCircularDeque = function(k) {
    
};

/**
 * @param {number} value
 * @return {boolean}
 */
MyCircularDeque.prototype.insertFront = function(value) {
    
};

/**
 * @param {number} value
 * @return {boolean}
 */
MyCircularDeque.prototype.insertLast = function(value) {
    
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteFront = function() {
    
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteLast = function() {
    
};

/**
 * @return {number}
 */
MyCircularDeque.prototype.getFront = function() {
    
};

/**
 * @return {number}
 */
MyCircularDeque.prototype.getRear = function() {
    
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.isEmpty = function() {
    
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.isFull = function() {
    
};

Sign in to run your own test cases

Sign in

Design Circular Deque — Solution in Python, Java & C++

Design Circular Deque solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Design Circular Deque is a medium coding problem on arrays and queue, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Arrays, Queue
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Implement a circular double-ended queue of fixed capacity, where elements can be added and removed at both ends, without using a built-in deque. Write the class MyCircularDeque:

  • MyCircularDeque(int k) creates a deque that holds at most k elements.
  • boolean insertFront(int value) / boolean insertLast(int value) add value at the front / back; they return true on success and false if the deque is full.
  • boolean deleteFront() / boolean deleteLast() remove the front / back element; they return true on success and false if the deque is empty.
  • int getFront() / int getRear() return the front / back element, or -1 if the deque is empty.
  • boolean isEmpty() / boolean isFull() report whether the deque is empty / full.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

Example 1

Input: ["MyCircularDeque","insertLast","insertLast","insertFront","insertFront","getRear","isFull","deleteLast","insertFront","getFront"]
[[3],[1],[2],[3],[4],[],[],[],[4],[]]
Output: [null,true,true,true,false,2,true,true,true,4]
Explanation: Capacity 3 holds [3,1,2]; inserting 4 at the front fails. The rear is 2. After deleteLast the deque is [3,1], so 4 fits at the front and becomes getFront.

Example 2

Input: ["MyCircularDeque","getFront","deleteLast","insertFront","insertLast","getRear","deleteFront","getFront","isEmpty"]
[[2],[],[],[5],[8],[],[],[],[]]
Output: [null,-1,false,true,true,8,true,8,false]
Explanation: An empty deque answers -1 and refuses to delete. After [5,8], the rear is 8; deleting the front leaves 8 at both ends.

Constraints

  • 1 <= k <= 1000
  • 0 <= value <= 1000
  • At most 2000 calls are made to insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty and isFull

Hints for Design Circular Deque

  1. Hint 1

    This is a circular queue that can also grow and shrink at the front.

  2. Hint 2

    Keep front (index of the first element) and count in an array of size k; the last element is at (front + count - 1) % k.

  3. Hint 3

    insertFront moves front one step back — (front - 1 + k) % k keeps it non-negative — and writes there; deleteFront moves it one step forward. The back end only changes count.

How to solve Design Circular Deque

A ring buffer with a front index and a count. Both ends are reachable in O(1): the front is front, the back is front + count - 1, each taken modulo k; adding at the front steps front backwards around the ring.

Approach

  1. Store buf of size k, front = 0, count = 0.
  2. insertFront(v): if full return false; front = (front - 1 + k) % k, buf[front] = v, count++.
  3. insertLast(v): if full return false; buf[(front + count) % k] = v, count++.
  4. deleteFront(): if empty return false; front = (front + 1) % k, count--. deleteLast(): if empty return false; count--.
  5. getFront() is buf[front], getRear() is buf[(front + count - 1) % k] (each -1 when empty); isEmpty / isFull compare count with 0 / k.

Why it works

The elements always occupy the count consecutive ring positions starting at front. Each operation either extends or shrinks that run by one slot at the appropriate end and leaves every other element in place, so the deque order is kept and no element is ever moved.

Complexity

  • Time — O(1) per operation
  • Space — O(k)

Pitfalls

  • (front - 1) % k is negative for front = 0 in C, C++, Java, Go, JavaScript and others — add k first.
  • Return -1 from getFront / getRear on an empty deque.

Reference solution

Python

class MyCircularDeque:

    def __init__(self, k: int):
        self.buf = [0] * k
        self.k = k
        self.front = 0
        self.count = 0

    def insertFront(self, value: int) -> bool:
        if self.count == self.k:
            return False
        self.front = (self.front - 1) % self.k
        self.buf[self.front] = value
        self.count += 1
        return True

    def insertLast(self, value: int) -> bool:
        if self.count == self.k:
            return False
        self.buf[(self.front + self.count) % self.k] = value
        self.count += 1
        return True

    def deleteFront(self) -> bool:
        if self.count == 0:
            return False
        self.front = (self.front + 1) % self.k
        self.count -= 1
        return True

    def deleteLast(self) -> bool:
        if self.count == 0:
            return False
        self.count -= 1
        return True

    def getFront(self) -> int:
        return self.buf[self.front] if self.count else -1

    def getRear(self) -> int:
        return self.buf[(self.front + self.count - 1) % self.k] if self.count else -1

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

    def isFull(self) -> bool:
        return self.count == self.k

Java

class MyCircularDeque {
    private int[] buf;
    private int k, front = 0, count = 0;

    public MyCircularDeque(int k) {
        this.k = k;
        buf = new int[k];
    }

    public boolean insertFront(int value) {
        if (count == k) return false;
        front = (front - 1 + k) % k;
        buf[front] = value;
        count++;
        return true;
    }

    public boolean insertLast(int value) {
        if (count == k) return false;
        buf[(front + count) % k] = value;
        count++;
        return true;
    }

    public boolean deleteFront() {
        if (count == 0) return false;
        front = (front + 1) % k;
        count--;
        return true;
    }

    public boolean deleteLast() {
        if (count == 0) return false;
        count--;
        return true;
    }

    public int getFront() {
        return count == 0 ? -1 : buf[front];
    }

    public int getRear() {
        return count == 0 ? -1 : buf[(front + count - 1) % k];
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public boolean isFull() {
        return count == k;
    }
}

C++

class MyCircularDeque {
    vector<int> buf;
    int k, front = 0, count = 0;
public:
    MyCircularDeque(int k) : buf(k), k(k) {}

    bool insertFront(int value) {
        if (count == k) return false;
        front = (front - 1 + k) % k;
        buf[front] = value;
        count++;
        return true;
    }

    bool insertLast(int value) {
        if (count == k) return false;
        buf[(front + count) % k] = value;
        count++;
        return true;
    }

    bool deleteFront() {
        if (count == 0) return false;
        front = (front + 1) % k;
        count--;
        return true;
    }

    bool deleteLast() {
        if (count == 0) return false;
        count--;
        return true;
    }

    int getFront() {
        return count == 0 ? -1 : buf[front];
    }

    int getRear() {
        return count == 0 ? -1 : buf[(front + count - 1) % k];
    }

    bool isEmpty() {
        return count == 0;
    }

    bool isFull() {
        return count == k;
    }
};

JavaScript

var MyCircularDeque = function(k) {
    this.k = k;
    this.buf = [];
    this.front = 0;
    this.count = 0;
};

MyCircularDeque.prototype.insertFront = function(value) {
    if (this.count === this.k) return false;
    this.front = (this.front - 1 + this.k) % this.k;
    this.buf[this.front] = value;
    this.count++;
    return true;
};

MyCircularDeque.prototype.insertLast = function(value) {
    if (this.count === this.k) return false;
    this.buf[(this.front + this.count) % this.k] = value;
    this.count++;
    return true;
};

MyCircularDeque.prototype.deleteFront = function() {
    if (this.count === 0) return false;
    this.front = (this.front + 1) % this.k;
    this.count--;
    return true;
};

MyCircularDeque.prototype.deleteLast = function() {
    if (this.count === 0) return false;
    this.count--;
    return true;
};

MyCircularDeque.prototype.getFront = function() {
    return this.count === 0 ? -1 : this.buf[this.front];
};

MyCircularDeque.prototype.getRear = function() {
    return this.count === 0 ? -1 : this.buf[(this.front + this.count - 1) % this.k];
};

MyCircularDeque.prototype.isEmpty = function() {
    return this.count === 0;
};

MyCircularDeque.prototype.isFull = function() {
    return this.count === this.k;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Queues and Deques