641. Design Circular Deque

MediumDesignQueueArrayLinked List
Leetcode Link

Problem Description

The given problem asks us to design a particular data structure known as a circular double-ended queue, often abbreviated as deque. A deque is a dynamic data structure that allows insertion and deletion of elements from both ends (front and back). The circular aspect of the queue implies that it is designed in such a way that the positions in the queue "wrap around" such that the last position is followed by the first, making the data structure continuous and circular.

Specifically, we need to implement a class MyCircularDeque with the following operations and their respective constraints:

  1. MyCircularDeque(int k) - Constructor which initializes the deque with a fixed maximum size k.
  2. boolean insertFront(int value) - Inserts an item at the front of the deque and returns true if successful or false if the deque is full.
  3. boolean insertLast(int value) - Inserts an item at the rear of the deque and also returns true if successful or false if the deque is full.
  4. boolean deleteFront() - Deletes an item from the front of the deque and returns true if the operation is successful or false if the deque is empty.
  5. boolean deleteLast() - Deletes an item from the rear of the deque with the same return semantics as deleteFront.
  6. int getFront() - Provides the front item from the deque, returning -1 if the deque is empty.
  7. int getRear() - Provides the rear item from the deque, again returning -1 if the deque is empty.
  8. boolean isEmpty() - Checks whether the deque is empty and returns true if it is, or false otherwise.
  9. boolean isFull() - Checks if the deque is full, returning true in such a case, or false otherwise.

The challenge is to implement a deque that uses fixed-size storage but operates as if it were dynamic thanks to its circular nature.

Intuition

To implement the MyCircularDeque, the solution should handle the "circular" part efficiently. Consequently, we use an array of size k to represent the deque and two pointers, one for the front of the deque and the other to keep track of the number of elements in the deque, referred to as size. Since the deque is circular, we need a strategy to navigate circularly within the fixed-size list, which is accomplished by using modulo arithmetic when updating the front pointer or calculating the index for insertions and deletions.

The intuition behind using modulo arithmetic is that when we reach the end of the array and need to wrap around to the beginning (or vice versa when going backwards), the modulo operation index % capacity will give us the correct index within the bounds of our fixed-size array.

During insertion at the front, we adjust the front index by subtracting one (to move to the front) and then use modulo to wrap around if necessary. Similarly, when inserting at the rear, we calculate the index based on front and size values. Deletion operations adjust the front index or reduce the size while avoiding underflow or overflow conditions.

For checking if the deque is full, we compare the size with the capacity. The deque is empty when size is zero. Peek operations at the front or rear involve calculating the index based on the front and size and then accessing the array element at that index, taking care to return -1 when the deque is empty.

Learn more about Queue and Linked List patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Solution Approach

The solution approach involves creating a fixed-size array and using two pointers ('front' and 'size') to efficiently manage the operations of the circular deque. Below is a detailed explanation of each operation implemented in MyCircularDeque class:

  1. Constructor (__init__): Initializes the deque with an array (self.q) of size k, self.front pointing to 0 (the initial position) and self.size to track the current number of elements. Also, self.capacity is set to k to enforce the fixed size of the deque.

  2. Insert Front (insertFront): When a new element is to be inserted at the front, first check if the deque is full using self.isFull(). If not full:

    • Adjust the front pointer one step backward using modulo operation: self.front = (self.front - 1 + self.capacity) % self.capacity.
    • Insert the new element at the front.
    • Increment size to reflect the addition.

  3. Insert Last (insertLast): To insert a new element at the rear, check if the deque is full. If there is space:

    • Calculate the new index for inserting the element at the rear using: idx = (self.front + self.size) % self.capacity.
    • Place the new element at the calculated idx.
    • Increase size accordingly.

  4. Delete Front (deleteFront): To delete the front element, first ensure that the deque is not empty by checking self.isEmpty(). If it contains elements:

    • Move the front pointer to the next element using the modulo operation: self.front = (self.front + 1) % self.capacity.
    • Decrease size.

  5. Delete Last (deleteLast): To remove the element at the rear, first check if the deque is empty. If it has elements:

    • No need to move any pointers because the next insertLast will overwrite the last element.
    • Simply decrement size.

  6. Get Front (getFront): Returns the value at the front of the deque. If empty, return -1. If not, return self.q[self.front].

  7. Get Rear (getRear): Returns the last element of the deque. If empty, return -1. If not, calculate the index of the rear element using: idx = (self.front + self.size - 1) % self.capacity, and return the element at this index.

  8. Is Empty (isEmpty): A simple check comparing self.size to 0 to determine if the deque is empty.

  9. Is Full (isFull): Check if the deque has reached its capacity by comparing self.size with self.capacity.

This implementation takes advantage of the modular arithmetic to wrap around the fixed-size array, thereby emulating a circular behavior. The array serves as the primary data structure, while the front and size pointers control access to the circular deque's elements.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a good use case for backtracking?

Example Walkthrough

Let's go through an example to illustrate how the MyCircularDeque operates using the solution approach.

Suppose we initialize our circular deque with a maximum size of 3.

  1. Initialization:

    • MyCircularDeque circularDeque = new MyCircularDeque(3); // set the size to be 3.
    • This creates an array q of size 3, sets front to 0, size to 0, and capacity to 3.

  2. Insert Last:

    • circularDeque.insertLast(1); // returns true.
    • The rear index is calculated as (front + size) % capacity which translates to (0 + 0) % 3 = 0.
    • The number 1 is inserted at index 0. The size is incremented to 1.

  3. Insert Last:

    • circularDeque.insertLast(2); // returns true.
    • The rear index is now (0 + 1) % 3 = 1.
    • The number 2 is inserted at index 1. The size is incremented to 2.

  4. Insert Front:

    • circularDeque.insertFront(3); // returns true.
    • front is adjusted backwards: (front - 1 + capacity) % capacity which translates to (0 - 1 + 3) % 3 = 2.
    • The number 3 is inserted at the new front which is index 2. The size is incremented to 3.

  5. Insert Front:

    • circularDeque.insertFront(4); // returns false, the deque is full.
    • Since size equals capacity (3), no insertion is possible and operation returns false.

  6. Get Rear:

    • circularDeque.getRear(); // returns 2.
    • The rear index is (front + size - 1) % capacity which is (2 + 3 - 1) % 3 = 1.
    • Index 1 has the value 2, which is returned.

  7. Is Full:

    • circularDeque.isFull(); // returns true.
    • This checks if size equals capacity which is 3 == 3, hence the deque is full.

  8. Delete Last:

    • circularDeque.deleteLast(); // returns true.
    • Removes the last element which is 2. size is decremented to 2.

  9. Insert Front:

    • circularDeque.insertFront(4); // returns true.
    • Adjust front backward to index 1 (new front after decrement is (2 - 1) % 3 = 1).
    • Insert number 4 at index 1. The size is incremented to 3.

  10. Get Front:

    • circularDeque.getFront(); // returns 4.
    • Since our front is currently at 1, and that's where we inserted the value 4 last, 4 is what gets returned.

The above step-by-step operations show how each method manipulates the front, size, and sometimes the capacity to perform their respective actions, while maintaining the integrity of a circular double-ended queue with fixed size. These examples also demonstrate how the operations are interdependent affecting the overall state of the queue.

Solution Implementation

1class MyCircularDeque:
2    def __init__(self, k: int):
3        """
4        Initialize the deque with a fixed size of 'k'.
5        """
6        self.queue = [0] * k
7        self.head = 0
8        self.size = 0
9        self.capacity = k
10
11    def insertFront(self, value: int) -> bool:
12        """
13        Add an item at the front of the deque.
14        Returns True if the operation is successful, otherwise False.
15        """
16        if self.isFull():
17            return False
18        if not self.isEmpty():
19            self.head = (self.head - 1 + self.capacity) % self.capacity
20        self.queue[self.head] = value
21        self.size += 1
22        return True
23
24    def insertLast(self, value: int) -> bool:
25        """
26        Add an item at the rear of the deque.
27        Returns True if the operation is successful, otherwise False.
28        """
29        if self.isFull():
30            return False
31        tail_index = (self.head + self.size) % self.capacity
32        self.queue[tail_index] = value
33        self.size += 1
34        return True
35
36    def deleteFront(self) -> bool:
37        """
38        Delete an item from the front of the deque.
39        Returns True if the operation is successful, otherwise False.
40        """
41        if self.isEmpty():
42            return False
43        self.head = (self.head + 1) % self.capacity
44        self.size -= 1
45        return True
46
47    def deleteLast(self) -> bool:
48        """
49        Delete an item from the rear of the deque.
50        Returns True if the operation is successful, otherwise False.
51        """
52        if self.isEmpty():
53            return False
54        self.size -= 1
55        return True
56
57    def getFront(self) -> int:
58        """
59        Get the front item from the deque.
60        Returns the front item, or -1 if the deque is empty.
61        """
62        if self.isEmpty():
63            return -1
64        return self.queue[self.head]
65
66    def getRear(self) -> int:
67        """
68        Get the last item from the deque.
69        Returns the last item, or -1 if the deque is empty.
70        """
71        if self.isEmpty():
72            return -1
73        tail_index = (self.head + self.size - 1) % self.capacity
74        return self.queue[tail_index]
75
76    def isEmpty(self) -> bool:
77        """
78        Check whether the deque is empty.
79        Returns True if the deque is empty, otherwise False.
80        """
81        return self.size == 0
82
83    def isFull(self) -> bool:
84        """
85        Check whether the deque is full.
86        Returns True if the deque is at full capacity, otherwise False.
87        """
88        return self.size == self.capacity
89
90# Example of how to use the MyCircularDeque class
91# circular_deque = MyCircularDeque(3)
92# print(circular_deque.insertLast(1))  # returns True
93# print(circular_deque.insertLast(2))  # returns True
94# print(circular_deque.insertFront(3)) # returns True
95# print(circular_deque.insertFront(4)) # returns False, the queue is full
96# print(circular_deque.getRear())      # returns 2
97# print(circular_deque.isFull())       # returns True
98# print(circular_deque.deleteLast())   # returns True
99# print(circular_deque.insertFront(4)) # returns True
100# print(circular_deque.getFront())     # returns 4
101
1class MyCircularDeque {
2    private int[] queue;
3    private int front;
4    private int size;
5    private int capacity;
6
7    /**
8     * Constructor to initialize the circular deque.
9     * @param k The capacity of the deque.
10     */
11    public MyCircularDeque(int k) {
12        queue = new int[k];
13        capacity = k;
14        front = 0;
15        size = 0;
16    }
17
18    /**
19     * Inserts an item at the front of the deque.
20     * @param value The value to insert.
21     * @return true if the operation is successful, false otherwise.
22     */
23    public boolean insertFront(int value) {
24        if (isFull()) {
25            return false;
26        }
27        front = (front - 1 + capacity) % capacity;
28        queue[front] = value;
29        size++;
30        return true;
31    }
32
33    /**
34     * Inserts an item at the rear of the deque.
35     * @param value The value to insert.
36     * @return true if the operation is successful, false otherwise.
37     */
38    public boolean insertLast(int value) {
39        if (isFull()) {
40            return false;
41        }
42        int rear = (front + size) % capacity;
43        queue[rear] = value;
44        size++;
45        return true;
46    }
47
48    /**
49     * Deletes an item from the front of the deque.
50     * @return true if the operation is successful, false otherwise.
51     */
52    public boolean deleteFront() {
53        if (isEmpty()) {
54            return false;
55        }
56        front = (front + 1) % capacity;
57        size--;
58        return true;
59    }
60
61    /**
62     * Deletes an item from the rear of the deque.
63     * @return true if the operation is successful, false otherwise.
64     */
65    public boolean deleteLast() {
66        if (isEmpty()) {
67            return false;
68        }
69        size--;
70        return true;
71    }
72
73    /**
74     * Gets the item from the front of the deque.
75     * @return The front item, or -1 if the deque is empty.
76     */
77    public int getFront() {
78        if (isEmpty()) {
79            return -1;
80        }
81        return queue[front];
82    }
83
84    /**
85     * Gets the item from the rear of the deque.
86     * @return The rear item, or -1 if the deque is empty.
87     */
88    public int getRear() {
89        if (isEmpty()) {
90            return -1;
91        }
92        int rear = (front + size - 1) % capacity;
93        return queue[rear];
94    }
95
96    /**
97     * Checks whether the circular deque is empty.
98     * @return true if the deque is empty, false otherwise.
99     */
100    public boolean isEmpty() {
101        return size == 0;
102    }
103
104    /**
105     * Checks whether the circular deque is full.
106     * @return true if the deque is full, false otherwise.
107     */
108    public boolean isFull() {
109        return size == capacity;
110    }
111}
112
1#include <vector>
2
3class MyCircularDeque {
4private:
5    std::vector<int> deque;   // Underlying container for the deque elements
6    int frontIndex;           // Index of the front element
7    int currentSize;          // Current number of elements in the deque
8    int maxCapacity;          // Maximum capacity of the deque
9
10public:
11    // Constructor to initialize the deque with a fixed capacity.
12    MyCircularDeque(int k) : frontIndex(0), currentSize(0), maxCapacity(k) {
13        deque.assign(k, 0);    // Initialize deque with zeros, using the specified capacity.
14    }
15
16    // Inserts an element at the front of the deque. Returns true if the operation is successful.
17    bool insertFront(int value) {
18        if (isFull()) {
19            return false; // Cannot insert when the deque is full.
20        }
21        // When not empty, decrement frontIndex circularly.
22        if (!isEmpty()) {
23            frontIndex = (frontIndex - 1 + maxCapacity) % maxCapacity;
24        }
25        deque[frontIndex] = value; // Assign value to new front position.
26        ++currentSize;             // Increment the size of the deque.
27        return true;
28    }
29
30    // Inserts an element at the rear of the deque. Returns true if the operation is successful.
31    bool insertLast(int value) {
32        if (isFull()) {
33            return false; // Cannot insert when the deque is full.
34        }
35        int rearIndex = (frontIndex + currentSize) % maxCapacity; // Calculate rear index.
36        deque[rearIndex] = value;  // Assign value to the rear position.
37        ++currentSize;             // Increment the size of the deque.
38        return true;
39    }
40
41    // Deletes an element from the front of the deque. Returns true if the operation is successful.
42    bool deleteFront() {
43        if (isEmpty()) {
44            return false; // Cannot delete when the deque is empty.
45        }
46        frontIndex = (frontIndex + 1) % maxCapacity; // Move front index forward circularly.
47        --currentSize;          // Decrement the size of the deque.
48        return true;
49    }
50
51    // Deletes an element from the rear of the deque. Returns true if the operation is successful.
52    bool deleteLast() {
53        if (isEmpty()) {
54            return false; // Cannot delete when the deque is empty.
55        }
56        --currentSize;  // Decrement the size of the deque. The rear element gets 'removed'.
57        return true;
58    }
59
60    // Gets the front item from the deque. Returns -1 if the deque is empty.
61    int getFront() {
62        return isEmpty() ? -1 : deque[frontIndex];
63    }
64
65    // Gets the last item from the deque. Returns -1 if the deque is empty.
66    int getRear() {
67        if (isEmpty()) {
68            return -1; // Return -1 when the deque is empty.
69        }
70        // Calculate the index of the last element and return the value.
71        int rearIndex = (frontIndex + currentSize - 1) % maxCapacity;
72        return deque[rearIndex];
73    }
74
75    // Checks whether the deque is empty.
76    bool isEmpty() {
77        return currentSize == 0;
78    }
79
80    // Checks whether the deque is full.
81    bool isFull() {
82        return currentSize == maxCapacity;
83    }
84};
85
86/**
87 * Usage of MyCircularDeque:
88 * MyCircularDeque* obj = new MyCircularDeque(k);
89 * bool param_1 = obj->insertFront(value);
90 * bool param_2 = obj->insertLast(value);
91 * bool param_3 = obj->deleteFront();
92 * bool param_4 = obj->deleteLast();
93 * int param_5 = obj->getFront();
94 * int param_6 = obj->getRear();
95 * bool param_7 = obj->isEmpty();
96 * bool param_8 = obj->isFull();
97 */
98
1const DEQUE_SIZE: number = 0;
2let deque_vals: number[] = [];
3let deque_start: number = 0;
4let deque_end: number = 0;
5let deque_length: number = 0;
6
7// Initializes the data structure with a maximum size 'k'.
8function initialize(k: number): void {
9    deque_vals = new Array(k).fill(0);
10    DEQUE_SIZE = k;
11    deque_start = 0;
12    deque_end = 0;
13    deque_length = 0;
14}
15
16// Inserts an element at the front of the deque. Returns true if the operation is successful.
17function insertFront(value: number): boolean {
18    if (isFull()) {
19        return false;
20    }
21    deque_start = deque_start === 0 ? DEQUE_SIZE - 1 : deque_start - 1;
22    deque_vals[deque_start] = value;
23    deque_length++;
24    return true;
25}
26
27// Inserts an element at the rear of the deque. Returns true if the operation is successful.
28function insertLast(value: number): boolean {
29    if (isFull()) {
30        return false;
31    }
32    deque_vals[deque_end] = value;
33    deque_end = (deque_end + 1) % DEQUE_SIZE;
34    deque_length++;
35    return true;
36}
37
38// Deletes an element from the front of the deque. Returns true if the operation is successful.
39function deleteFront(): boolean {
40    if (isEmpty()) {
41        return false;
42    }
43    deque_start = (deque_start + 1) % DEQUE_SIZE;
44    deque_length--;
45    return true;
46}
47
48// Deletes an element from the rear of the deque. Returns true if the operation is successful.
49function deleteLast(): boolean {
50    if (isEmpty()) {
51        return false;
52    }
53    deque_end = deque_end === 0 ? DEQUE_SIZE - 1 : deque_end - 1;
54    deque_length--;
55    return true;
56}
57
58// Gets the front item from the deque. Returns -1 if the deque is empty.
59function getFront(): number {
60    if (isEmpty()) {
61        return -1;
62    }
63    return deque_vals[deque_start];
64}
65
66// Gets the last item from the deque. Returns -1 if the deque is empty.
67function getRear(): number {
68    if (isEmpty()) {
69        return -1;
70    }
71    let last_index = deque_end === 0 ? DEQUE_SIZE - 1 : deque_end - 1;
72    return deque_vals[last_index];
73}
74
75// Checks whether the deque is empty or not.
76function isEmpty(): boolean {
77    return deque_length === 0;
78}
79
80// Checks whether the deque is full or not.
81function isFull(): boolean {
82    return deque_length === DEQUE_SIZE;
83}
84
Not Sure What to Study? Take the 2-min Quiz：

How does quick sort divide the problem into subproblems?

Time and Space Complexity

Time Complexity

  • __init__(k: int): The initialization of the deque takes O(k) time since it initializes a list of size k with zeros.
  • insertFront(value: int) -> bool: Inserting an item at the front takes O(1) time as it is done by updating an index and inserting the value.
  • insertLast(value: int) -> bool: Inserting an item at the rear is also done in O(1) time, which involves calculating the index and inserting the value.
  • deleteFront() -> bool: Deleting an item from the front takes O(1) time due to the update of the front index and decreasing the size.
  • deleteLast() -> bool: Deleting an item from the rear takes O(1) time since it only involves decrementing the size.
  • getFront() -> int: Retrieving the front item is O(1) because it simply accesses the element at the front index.
  • getRear() -> int: Retrieving the rear item is O(1) by calculating the index of the last item based on front and size and then accessing it.
  • isEmpty() -> bool: Checking if the deque is empty takes O(1) time as it checks if the size is 0.
  • isFull() -> bool: Checking if the deque is full also takes O(1) time by comparing size and capacity.

All operations of the deque are implemented in a way that ensures a constant time complexity.

Space Complexity

  • The overall space complexity for the deque is O(k), which is required for storing the elements of the deque. The variables front, size, and capacity use constant additional space, hence they do not affect the overall space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Recommended Readings

Queue Intro

Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫