LeetCode 641: Design Circular Deque Solution

Master LeetCode problem 641 (Design Circular Deque), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

641. Design Circular Deque

Medium

Array Linked List Design Queue

Problem Explanation

Explanation

To design a circular deque, we can use a doubly linked list where each node represents an element in the deque. We will also maintain pointers to the front and rear of the deque for easy insertion and deletion operations.

For each operation provided in the problem statement, we will implement the necessary functionality to maintain the circular nature of the deque. We will handle edge cases such as checking if the deque is full or empty.

Time Complexity:

Insertion and deletion operations: O(1)
Checking if the deque is full or empty: O(1)

Space Complexity:

O(k) where k is the maximum size of the deque.

Solution Code

class MyCircularDeque {
    class Node {
        int val;
        Node next;
        Node prev;
        public Node(int val) {
            this.val = val;
        }
    }
    
    Node front;
    Node rear;
    int capacity;
    int size;
    
    public MyCircularDeque(int k) {
        capacity = k;
        size = 0;
        front = new Node(-1);
        rear = new Node(-1);
        front.next = rear;
        rear.prev = front;
    }
    
    public boolean insertFront(int value) {
        if (isFull()) return false;
        Node newNode = new Node(value);
        newNode.next = front.next;
        newNode.prev = front;
        front.next.prev = newNode;
        front.next = newNode;
        size++;
        return true;
    }
    
    public boolean insertLast(int value) {
        if (isFull()) return false;
        Node newNode = new Node(value);
        newNode.prev = rear.prev;
        newNode.next = rear;
        rear.prev.next = newNode;
        rear.prev = newNode;
        size++;
        return true;
    }
    
    public boolean deleteFront() {
        if (isEmpty()) return false;
        Node toDelete = front.next;
        front.next = toDelete.next;
        toDelete.next.prev = front;
        size--;
        return true;
    }
    
    public boolean deleteLast() {
        if (isEmpty()) return false;
        Node toDelete = rear.prev;
        rear.prev = toDelete.prev;
        toDelete.prev.next = rear;
        size--;
        return true;
    }
    
    public int getFront() {
        return front.next.val;
    }
    
    public int getRear() {
        return rear.prev.val;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size == capacity;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 641 (Design Circular Deque)?

This page provides optimized solutions for LeetCode problem 641 (Design Circular Deque) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 641 (Design Circular Deque)?

The time complexity for LeetCode 641 (Design Circular Deque) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 641 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 641 in Java, C++, or Python.

Back to LeetCode Solutions