grid47 Exploring patterns and algorithms
Sep 3, 2024
8 min read
Solution to LeetCode 641: Design Circular Deque Problem
Design a data structure that simulates a circular double-ended queue (deque) with a fixed maximum size. Implement the MyCircularDeque class with methods for inserting, deleting, and accessing elements at both ends of the deque.
Problem
Approach
Steps
Complexity
Input: The input consists of multiple operations to be executed on the deque. Each operation is an array with the first element being the method name and the following elements representing the arguments.
Output: For each method call, return the result of the operation. If the operation is successful, return a boolean value. For 'getFront' and 'getRear', return the respective item, or -1 if the deque is empty.
• Explanation: This example shows the correct sequence of operations on a circular deque, handling insertion, deletion, and retrieval of elements with a fixed size.
Approach: We can implement the circular deque using an array with two pointers (front and back), ensuring efficient insertions and deletions at both ends by updating the pointers using modulo arithmetic.
Observations:
• A circular array can efficiently handle the required operations.
• The modulo operation helps to wrap around the array when inserting or deleting elements.
• We can use a fixed-size array and two pointers to simulate the circular behavior.
Steps:
• Initialize the deque with a fixed size and two pointers (front and back).
• Implement methods for insertion, deletion, and retrieval, adjusting the pointers appropriately.
• Use modulo arithmetic to ensure the circular nature of the deque.
Empty Inputs:
• Ensure that operations like 'getFront' and 'getRear' handle an empty deque correctly by returning -1.
Large Inputs:
• Ensure the solution works efficiently for the largest possible size of the deque and the maximum number of operations.
Special Values:
• Consider cases where the deque is full or empty before performing operations.
Constraints:
• The implementation should be able to handle up to 2000 operations efficiently.
Constructor that initializes the circular deque with a given size 'k', setting the front and back indices, and initializing the count of elements to zero.
5 : Insert Front Method
boolinsertFront(int value) {
Defines the 'insertFront' method that inserts an element at the front of the deque.
6 : Full Check
if(isFull()) returnfalse;
Checks if the deque is full before inserting a new element.
7 : Insert Element
buf[frd] = value;
Inserts the value at the front of the deque.
8 : Update Front Index
frd = (frd -1+ sz) % sz;
Updates the front index after inserting the element, wrapping it around if necessary.
9 : Increment Count
++cnt;
Increments the count of elements in the deque.
10 : Return True
returntrue;
Returns true indicating the insertion was successful.
11 : Insert Last Method
boolinsertLast(int value) {
Defines the 'insertLast' method that inserts an element at the back of the deque.
12 : Full Check
if(isFull()) returnfalse;
Checks if the deque is full before inserting a new element.
13 : Insert Element
buf[bck] = value;
Inserts the value at the back of the deque.
14 : Update Back Index
bck = (bck +1) % sz;
Updates the back index after inserting the element, wrapping it around if necessary.
15 : Increment Count
++cnt;
Increments the count of elements in the deque.
16 : Return True
returntrue;
Returns true indicating the insertion was successful.
17 : Delete Front Method
booldeleteFront() {
Defines the 'deleteFront' method that removes an element from the front of the deque.
18 : Empty Check
if(isEmpty()) returnfalse;
Checks if the deque is empty before attempting to delete an element.
19 : Update Front Index
frd = (frd +1) % sz;
Updates the front index after deleting the element, wrapping it around if necessary.
20 : Decrement Count
--cnt;
Decrements the count of elements in the deque.
21 : Return True
returntrue;
Returns true indicating the deletion was successful.
22 : Delete Last Method
booldeleteLast() {
Defines the 'deleteLast' method that removes an element from the back of the deque.
23 : Empty Check
if(isEmpty()) returnfalse;
Checks if the deque is empty before attempting to delete an element.
24 : Update Back Index
bck = (bck -1+ sz) % sz;
Updates the back index after deleting the element, wrapping it around if necessary.
25 : Decrement Count
--cnt;
Decrements the count of elements in the deque.
26 : Return True
returntrue;
Returns true indicating the deletion was successful.
27 : Get Front Method
intgetFront() {
Defines the 'getFront' method that retrieves the element at the front of the deque.
28 : Empty Check
if(isEmpty()) return-1;
Checks if the deque is empty before attempting to get an element.
29 : Return Front Element
return buf[(frd +1) % sz];
Returns the element at the front of the deque.
30 : Get Rear Method
intgetRear() {
Defines the 'getRear' method that retrieves the element at the back of the deque.
31 : Empty Check
if(isEmpty()) return-1;
Checks if the deque is empty before attempting to get an element.
32 : Return Rear Element
return buf[(bck -1+ sz) % sz];
Returns the element at the back of the deque.
33 : Is Empty Method
boolisEmpty() {
Defines the 'isEmpty' method that checks if the deque is empty.
34 : Return Empty Status
return cnt ==0;
Returns true if the deque is empty.
35 : Is Full Method
boolisFull() {
Defines the 'isFull' method that checks if the deque is full.
36 : Return Full Status
return cnt == sz;
Returns true if the deque is full.
Best Case: O(1)
Average Case: O(1)
Worst Case: O(1)
Description: Each operation (insert, delete, get) is performed in constant time due to the circular nature of the deque.
Best Case: O(k)
Worst Case: O(k)
Description: The space complexity is O(k) where k is the maximum size of the deque, as we need to store up to k elements.
