algoadvance

Leetcode 641. Design Circular Deque

Problem Statement

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(int value) Adds an item at the front of Deque. Return true if the operation is successful, or false otherwise.
• boolean insertLast(int value) Adds an item at the rear of Deque. Return true if the operation is successful, or false otherwise.
• boolean deleteFront() Deletes an item from the front of Deque. Return true if the operation is successful, or false otherwise.
• boolean deleteLast() Deletes an item from the rear of Deque. Return true if the operation is successful, or false otherwise.
• int getFront() Returns the front item from the Deque. Return -1 if the deque is empty.
• int getRear() Returns the last item from the Deque. Return -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.

Clarifying Questions

1. Is it guaranteed that all operations are valid?
   • No, we must handle invalid operations gracefully and return the appropriate boolean value.
2. What data structure should be used to implement the deque?
   • We will use a circular array to implement the deque functionality.

Code

#include <vector>

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

public:
    MyCircularDeque(int k) : deque(k), front(0), rear(0), size(0), capacity(k) {}

    bool insertFront(int value) {
        if (isFull()) return false;

        front = (front - 1 + capacity) % capacity;
        deque[front] = value;
        size++;
        return true;
    }

    bool insertLast(int value) {
        if (isFull()) return false;

        deque[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 deque[front];
    }

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

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

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

Strategy

1. Initialization:
   • Use a vector deque to store the elements with a fixed size capacity.
   • Maintain two pointers front and rear to track the front and rear ends of the deque.
   • Maintain a size variable to track the number of elements in the deque.
2. Insertions:
   • For insertFront, adjust the front pointer and insert the value. Use modular arithmetic to handle wrapping around.
   • For insertLast, insert the value at the rear pointer and adjust it with modular arithmetic.
3. Deletions:
   • For deleteFront, adjust the front pointer using modular arithmetic.
   • For deleteLast, adjust the rear pointer using modular arithmetic.
4. Access Methods:
   • getFront returns the element at the front pointer.
   • getRear returns the last element added, which is one element before the rear pointer, adjusted for wrap-around.
5. State Check:
   • isEmpty checks if the size is 0.
   • isFull checks if the size equals the capacity.

Time Complexity

• All operations (insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull) are O(1) because they involve only a constant amount of operations irrespective of the number of elements in the deque.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?