Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Design Circular Deque

Try it yourself
MediumProblemExternal link

Description

Design a double-ended queue, a deque, that holds at most k values and can add and remove at both ends. Implement MyCircularDeque:

  • MyCircularDeque(int k) starts an empty deque with room for k values.
  • insertFront(int value) and insertLast(int value) add a value at the front or the back. They return true, or false if the deque is already full.
  • deleteFront() and deleteLast() remove the front or the back value. They return true, or false if the deque is empty.
  • getFront() and getRear() return the front or the back value, or -1 if the deque is empty.
  • isEmpty() and isFull() say whether the deque holds no values, or k of them.

Examples

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: Room for 3: 1 and 2 go in at the back and 3 at the front, so the deque is 3, 1, 2 and full; inserting 4 is refused. The rear is 2. Deleting it leaves room, and 4 goes in at the front: 4, 3, 1.

Example 2

Input:

["MyCircularDeque", "insertFront", "getFront", "getRear", "insertLast", "deleteFront", "isEmpty", "getRear"]
[[1], [7], [], [], [8], [], [], []]

Output: [null, true, 7, 7, false, true, true, -1]

Explanation: With room for one value, the front and the rear are the same value. Once it's removed, the deque is empty and the rear reads −1.

Example 3

Input:

["MyCircularDeque", "deleteFront", "deleteLast", "getFront", "isEmpty", "insertLast", "isFull"]
[[2], [], [], [], [], [5], []]

Output: [null, false, false, -1, true, true, false]

Explanation: Deleting from an empty deque returns false, and reading it returns −1.

Constraints

  • 1 ≤ k ≤ 1000
  • 0 ≤ value ≤ 1000
  • At most 2000 calls will be made to insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty and isFull

Editorial

Brute Force

Intuition

Keep the values in an ordinary list, front first, and check its length against k. The back is easy: append and pop at the end. The front works too, by inserting at index 0 and removing index 0, but each of those moves every other value one place.

Step-by-Step Explanation

Let's trace Example 1, with room for 3:

  1. insertLast(1): 1 goes on the end, and nothing else moves.
  2. insertLast(2): 2 goes on the end, and nothing else moves.
  3. insertFront(3): 3 goes in at index 0, and the 2 values after it each move one place.
  4. insertFront(4) returns false, because the list already holds 3.
  5. getRear() returns 2.
  6. isFull() returns true.
  7. deleteLast(): the last value comes out, and nothing else moves.
  8. insertFront(4): 4 goes in at index 0, and the 2 values after it each move one place.
  9. getFront() returns 4.

A List, Front First — Inserts and deletes at the front shift every value behind them.

Algorithm

  1. Keep a list items, front first, and the capacity k.
  2. insertFront and insertLast: refuse if len(items) == k; otherwise insert at index 0 or append.
  3. deleteFront and deleteLast: refuse if the list is empty; otherwise remove index 0 or the last value.
  4. getFront and getRear read the ends, or return −1; isEmpty and isFull compare the length with 0 and k.

Code

class MyCircularDeque {
    int k;
    vector<int> items;                       // front first
public:
    MyCircularDeque(int k) : k(k) {}

    bool insertFront(int value) {
        if ((int)items.size() == k) return false;
        items.insert(items.begin(), value);  // every value moves one place right
        return true;
    }

    bool insertLast(int value) {
        if ((int)items.size() == k) return false;
        items.push_back(value);
        return true;
    }

    bool deleteFront() {
        if (items.empty()) return false;
        items.erase(items.begin());          // every value moves one place left
        return true;
    }

    bool deleteLast() {
        if (items.empty()) return false;
        items.pop_back();
        return true;
    }

    int getFront() { return items.empty() ? -1 : items.front(); }
    int getRear() { return items.empty() ? -1 : items.back(); }
    bool isEmpty() { return items.empty(); }
    bool isFull() { return (int)items.size() == k; }
};

class MyCircularDeque:
    def __init__(self, k: int):
        self.k = k
        self.items = []                      # front first

    def insertFront(self, value: int) -> bool:
        if len(self.items) == self.k:
            return False
        self.items.insert(0, value)          # every value moves one place right
        return True

    def insertLast(self, value: int) -> bool:
        if len(self.items) == self.k:
            return False
        self.items.append(value)
        return True

    def deleteFront(self) -> bool:
        if not self.items:
            return False
        self.items.pop(0)                    # every value moves one place left
        return True

    def deleteLast(self) -> bool:
        if not self.items:
            return False
        self.items.pop()
        return True

    def getFront(self) -> int:
        return self.items[0] if self.items else -1

    def getRear(self) -> int:
        return self.items[-1] if self.items else -1

    def isEmpty(self) -> bool:
        return not self.items

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

class MyCircularDeque {
    private final int k;
    private final List<Integer> items = new ArrayList<>();   // front first

    public MyCircularDeque(int k) {
        this.k = k;
    }

    public boolean insertFront(int value) {
        if (items.size() == k) return false;
        items.add(0, value);                                  // every value moves one place right
        return true;
    }

    public boolean insertLast(int value) {
        if (items.size() == k) return false;
        items.add(value);
        return true;
    }

    public boolean deleteFront() {
        if (items.isEmpty()) return false;
        items.remove(0);                                      // every value moves one place left
        return true;
    }

    public boolean deleteLast() {
        if (items.isEmpty()) return false;
        items.remove(items.size() - 1);
        return true;
    }

    public int getFront() { return items.isEmpty() ? -1 : items.get(0); }
    public int getRear() { return items.isEmpty() ? -1 : items.get(items.size() - 1); }
    public boolean isEmpty() { return items.isEmpty(); }
    public boolean isFull() { return items.size() == k; }
}

var MyCircularDeque = function(k) {
    this.k = k;
    this.items = [];                         // front first
};

MyCircularDeque.prototype.insertFront = function(value) {
    if (this.items.length === this.k) return false;
    this.items.unshift(value);               // every value moves one place right
    return true;
};

MyCircularDeque.prototype.insertLast = function(value) {
    if (this.items.length === this.k) return false;
    this.items.push(value);
    return true;
};

MyCircularDeque.prototype.deleteFront = function() {
    if (this.items.length === 0) return false;
    this.items.shift();                      // every value moves one place left
    return true;
};

MyCircularDeque.prototype.deleteLast = function() {
    if (this.items.length === 0) return false;
    this.items.pop();
    return true;
};

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

MyCircularDeque.prototype.getRear = function() {
    return this.items.length ? this.items[this.items.length - 1] : -1;
};

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

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

Complexity Analysis

Time Complexity: O(k) for each insert or delete at the front, O(1) for everything else

Inserting or deleting at index 0 moves up to k − 1 values.

Space Complexity: O(k)

At most k values.

Why This Approach Is Not Efficient

At these limits it still fits: 2,000 calls that each move up to 999 values is about 2 × 10^6 moves. But a deque is supposed to be cheap at both ends, and this one isn't: the cost of a front operation grows with the capacity.

The values never need to move. Fix them in k slots used as a circle and move only the ends: a head index for the front, and a count, so the back is (head + count - 1) % k. Adding at the front steps head back one slot, wrapping from slot 0 to slot k − 1.

Optimal Approach - A Ring Buffer

Intuition

Use an array of k slots, the index head of the front value, and count, the number of values. The count tells full (count == k) from empty (count == 0), which head alone can't.

  • insertLast writes the slot after the back, (head + count) % k, and adds one to count.
  • insertFront steps head back, (head - 1 + k) % k, writes there, and adds one to count. The + k keeps the index from going negative in languages whose % keeps the sign.
  • deleteFront moves head forward; deleteLast only lowers count.
  • The back value is at (head + count - 1) % k.

Step-by-Step Explanation

Let's trace Example 1, with room for 3:

  1. insertLast(1): the slot after the back is (0 + 0) % 3, slot 0.
  2. insertLast(2): the slot after the back is (0 + 1) % 3, slot 1.
  3. insertFront(3): head steps back from slot 0, (0 - 1 + 3) % 3, to slot 2, and 3 goes there.
  4. insertFront(4) returns false, because count is 3 and every slot is in use.
  5. getRear() reads the back, (2 + 3 - 1) % 3, slot 1: 2.
  6. isFull() returns true, since count is 3 of 3.
  7. deleteLast(): count drops to 2, so slot 1 is free again. Nothing moves.
  8. insertFront(4): head steps back from slot 2, (2 - 1 + 3) % 3, to slot 1, and 4 goes there.
  9. getFront() reads slot 1: 4.

Three Slots in a Circle — Only `head` and the back move; the values stay in their slots.

Algorithm

  1. Keep data with k slots, head = 0 and count = 0.
  2. insertFront: refuse if count == k; else head = (head - 1 + k) % k, data[head] = value, count += 1.
  3. insertLast: refuse if count == k; else data[(head + count) % k] = value, count += 1.
  4. deleteFront: refuse if count == 0; else head = (head + 1) % k, count -= 1. deleteLast: refuse if count == 0; else count -= 1.
  5. getFront reads data[head] and getRear reads data[(head + count - 1) % k], or −1 when count == 0.

Code

class MyCircularDeque {
    vector<int> data;                        // the slots, reused in a circle
    int head = 0;                            // index of the front value
    int count = 0;                           // how many values are stored
public:
    MyCircularDeque(int k) : data(k) {}

    bool insertFront(int value) {
        if (count == (int)data.size()) return false;
        head = (head - 1 + data.size()) % data.size();       // step back, wrapping
        data[head] = value;
        count++;
        return true;
    }

    bool insertLast(int value) {
        if (count == (int)data.size()) return false;
        data[(head + count) % data.size()] = value;         // the slot after the back
        count++;
        return true;
    }

    bool deleteFront() {
        if (count == 0) return false;
        head = (head + 1) % data.size();
        count--;
        return true;
    }

    bool deleteLast() {
        if (count == 0) return false;
        count--;                                            // the back slot simply stops being counted
        return true;
    }

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

    int getRear() {
        return count == 0 ? -1 : data[(head + count - 1) % data.size()];
    }

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

    bool isFull() {
        return count == (int)data.size();
    }
};

class MyCircularDeque:
    def __init__(self, k: int):
        self.data = [0] * k                  # the slots, reused in a circle
        self.head = 0                        # index of the front value
        self.count = 0                       # how many values are stored

    def insertFront(self, value: int) -> bool:
        if self.count == len(self.data):
            return False
        self.head = (self.head - 1 + len(self.data)) % len(self.data)   # step back, wrapping
        self.data[self.head] = value
        self.count += 1
        return True

    def insertLast(self, value: int) -> bool:
        if self.count == len(self.data):
            return False
        self.data[(self.head + self.count) % len(self.data)] = value   # the slot after the back
        self.count += 1
        return True

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

    def deleteLast(self) -> bool:
        if self.count == 0:
            return False
        self.count -= 1                      # the back slot simply stops being counted
        return True

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

    def getRear(self) -> int:
        return self.data[(self.head + self.count - 1) % len(self.data)] if self.count else -1

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

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

class MyCircularDeque {
    private final int[] data;                // the slots, reused in a circle
    private int head = 0;                    // index of the front value
    private int count = 0;                   // how many values are stored

    public MyCircularDeque(int k) {
        data = new int[k];
    }

    public boolean insertFront(int value) {
        if (count == data.length) return false;
        head = (head - 1 + data.length) % data.length;       // step back, wrapping
        data[head] = value;
        count++;
        return true;
    }

    public boolean insertLast(int value) {
        if (count == data.length) return false;
        data[(head + count) % data.length] = value;         // the slot after the back
        count++;
        return true;
    }

    public boolean deleteFront() {
        if (count == 0) return false;
        head = (head + 1) % data.length;
        count--;
        return true;
    }

    public boolean deleteLast() {
        if (count == 0) return false;
        count--;                                            // the back slot simply stops being counted
        return true;
    }

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

    public int getRear() {
        return count == 0 ? -1 : data[(head + count - 1) % data.length];
    }

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

    public boolean isFull() {
        return count == data.length;
    }
}

var MyCircularDeque = function(k) {
    this.data = new Array(k).fill(0);        // the slots, reused in a circle
    this.head = 0;                           // index of the front value
    this.count = 0;                          // how many values are stored
};

MyCircularDeque.prototype.insertFront = function(value) {
    if (this.count === this.data.length) return false;
    this.head = (this.head - 1 + this.data.length) % this.data.length;   // step back, wrapping
    this.data[this.head] = value;
    this.count++;
    return true;
};

MyCircularDeque.prototype.insertLast = function(value) {
    if (this.count === this.data.length) return false;
    this.data[(this.head + this.count) % this.data.length] = value;     // the slot after the back
    this.count++;
    return true;
};

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

MyCircularDeque.prototype.deleteLast = function() {
    if (this.count === 0) return false;
    this.count--;                            // the back slot simply stops being counted
    return true;
};

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

MyCircularDeque.prototype.getRear = function() {
    return this.count ? this.data[(this.head + this.count - 1) % this.data.length] : -1;
};

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

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

Complexity Analysis

Time Complexity: O(1) per call

Each call does a few index operations; nothing is shifted.

Space Complexity: O(k)

The k slots, allocated once.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Reading the rear at the next free slot. return self.data[(self.head + self.count) % len(self.data)] if self.count else -1

On Example 1 it returns [null, true, true, true, false, 3, true, true, true, 4]; the answer is [null, true, true, true, false, 2, true, true, true, 4]. (head + count) % k is the next free slot, one past the back. The rear value is in the slot before it: (head + count - 1) % k.

Stepping back without adding k. head = (head - 1) % data.length; (in Java)

On Example 1 it crashes with ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 3; the answer is [null, true, true, true, false, 2, true, true, true, 4]. In Java, C++ and JavaScript, % keeps the sign of the left side, so (0 - 1) % k is −1, not k − 1, and the first insert at the front writes outside the array. Add k before taking the remainder: (head - 1 + k) % k.

Keeping a slot unused in only k slots. return (self.tail + 1) % len(self.data) == self.head

On Example 1 it returns [null, true, true, false, false, 2, true, true, true, 4]; the answer is [null, true, true, true, false, 2, true, true, true, 4]. Without a count, head == tail means empty, so a full deque has to keep one slot unused to look different. That needs k + 1 slots; with only k, the deque refuses the k-th value. Keep a count, or allocate one slot more.

Where This Pattern Is Taught

This problem practises the ring buffer at both ends. It's taught in Introduction to Queues, along with why the count is kept and why stepping back needs the + k. Design Circular Queue is the same ring with one open end.