• Posts

Problem 641 Design Circular Deque

Problem Statement

Link - Problem 641

Question

Design your implementation of the circular double-ended queue (deque).

Implement the MyCircularDeque class:

• MyCircularDeque(int k) Initializes the deque with a maximum size of k.
• boolean insertFront() Adds an item at the front of Deque. Returns true if the operation is successful, or false otherwise.
• boolean insertLast() Adds an item at the rear of Deque. Returns true if the operation is successful, or false otherwise.
• boolean deleteFront() Deletes an item from the front of Deque. Returns true if the operation is successful, or false otherwise.
• boolean deleteLast() Deletes an item from the rear of Deque. Returns true if the operation is successful, or false otherwise.
• int getFront() Returns the front item from the Deque. Returns -1 if the deque is empty.
• int getRear() Returns the last item from Deque. Returns -1 if the deque is empty.
• boolean isEmpty() Returns true if the deque is empty, or false otherwise.
• boolean isFull() Returns true if the deque is full, or false otherwise.

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
MyCircularDeque myCircularDeque = new MyCircularDeque(3);
myCircularDeque.insertLast(1);  // return True
myCircularDeque.insertLast(2);  // return True
myCircularDeque.insertFront(3); // return True
myCircularDeque.insertFront(4); // return False, the queue is full.
myCircularDeque.getRear();      // return 2
myCircularDeque.isFull();       // return True
myCircularDeque.deleteLast();   // return True
myCircularDeque.insertFront(4); // return True
myCircularDeque.getFront();     // return 4

Constraints:

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

Solution

class MyCircularDeque {
private:
    vector<int>arr;
    int front;
    int rear;
    int capacity;
    int size;

public:
    MyCircularDeque(int k) {
        capacity = k;
        arr.resize(capacity);
        front = 0;
        rear = 0;
        size = 0;
    }

    bool insertFront(int value) {
        if (isFull())
            return false;
        front = (front - 1 + capacity) % capacity;
        arr[front] = value;
        size++;
        return true;
    }

    bool insertLast(int value) {
        if (isFull())
            return false;
        arr[rear] = value;
        rear = (rear + 1) % capacity;
        size++;
        return true;
    }

    bool deleteFront() {
        if (isEmpty())
            return false;
        front = (front + 1) % capacity;
        size--;
        return true;
    }

    bool deleteLast() {
        if (isEmpty())
            return false;
        rear = (rear - 1 + capacity) % capacity;
        size--;
        return true;
    }

    int getFront() {
        if (isEmpty())
            return -1;
        return arr[front];
    }

    int getRear() {
        if (isEmpty())
            return -1;
        return arr[(rear - 1 + capacity) % capacity];
    }

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

    bool isFull() {
        return size == capacity;
    }

};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */

Complexity Analysis

| Algorithm                     | Time Complexity | Space Complexity |
| ----------------------------- | --------------- | ---------------- |
| Circular Array Implementation | O(1)            | O(k)             |

Explanation

Intial Thoughts

To approach this problem, consider a circular buffer where elements can be added or removed from both ends. Think of it as a merry-go-round where you can get on or off at either end. Start by initializing the deque with a maximum size, and keep track of the front and rear pointers. Consider how to handle cases where the deque is full or empty. Think about how to update the front and rear pointers when elements are added or removed.

Intuitive Analysis

Intuitively, solving this problem involves understanding how a circular deque works. Imagine a ring where you can insert or delete elements at any point. To insert an element at the front, move the front pointer backwards and add the element. To insert at the rear, move the rear pointer forwards and add the element. When deleting, move the corresponding pointer in the opposite direction. Keep track of the size of the deque to handle full or empty cases. Visualize the process like a circular train where cars can be added or removed at either end, and the train can wrap around itself.

1. Intuition

• To implement a circular double-ended queue, we need to consider the properties of a deque and how to efficiently add and remove elements from both ends.
• We should use a circular array to store the elements, which allows us to reuse the space when an element is removed from the front or rear.
• The front and rear pointers are used to keep track of the current front and rear of the deque, and they are updated accordingly when elements are added or removed.
• The size variable keeps track of the current number of elements in the deque, which helps us to determine whether the deque is empty or full.
• The capacity variable stores the maximum size of the deque, which is used to check whether the deque is full before adding a new element.
• The circular nature of the deque allows us to use the modulo operator to wrap around the array when the front or rear pointer reaches the end of the array.
• This implementation provides an efficient way to add and remove elements from both ends of the deque, with an average time complexity of O(1).
• The use of a circular array and the front and rear pointers enables us to implement the deque operations in a concise and efficient manner.

2. Implementation

• The MyCircularDeque class is initialized with a maximum size k, and the arr vector is resized to k to store the elements.
• The insertFront method checks if the deque is full using the isFull method, and if not, it updates the front pointer and adds the new element to the front of the deque using arr[front] = value.
• The insertLast method checks if the deque is full, and if not, it adds the new element to the rear of the deque using arr[rear] = value and updates the rear pointer using rear = (rear + 1) % capacity.
• The deleteFront method checks if the deque is empty, and if not, it updates the front pointer using front = (front + 1) % capacity to remove the front element.
• The deleteLast method checks if the deque is empty, and if not, it updates the rear pointer using rear = (rear - 1 + capacity) % capacity to remove the rear element.
• The getFront and getRear methods return the front and rear elements of the deque, respectively, using arr[front] and arr[(rear - 1 + capacity) % capacity].
• The isEmpty and isFull methods check whether the deque is empty or full, respectively, using the size variable.
• The implementation uses the modulo operator to handle the circular nature of the deque, ensuring that the front and rear pointers wrap around the array correctly.

Complexity Analysis

Time Complexity:

• All operations such as insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, and isFull are performed in constant time, O(1), as they only involve updating indices and checking conditions without any loops or recursive calls.
• The dominant operations are the updates of front, rear, and size variables, which are constant time operations as they involve simple arithmetic and assignment operations.
• The justification of the Big O classification as O(1) stems from the fact that none of the operations depend on the size of the input, ‘k’, and all operations can be completed in a fixed amount of time regardless of the size of the input.

Space Complexity:

• The algorithm uses a circular array of size ‘k’ to store the elements, resulting in a space complexity of O(k) as the memory usage grows linearly with the size of the input.
• The data structure used, a vector arr, has a direct impact on the space complexity as it requires ‘k’ amount of space to store ‘k’ elements, hence the space complexity is O(k).
• The justification of the space complexity as O(k) comes from the fact that the algorithm allocates a fixed amount of space at the beginning, which is proportional to the input size ‘k’, and does not change throughout the execution.

Footnote

This question is rated as Medium difficulty.

Similar Questions: