Problem of The Day: Design Circular Deque
Problem Statement
Intuition
The problem is to implement a circular deque using a doubly linked list structure. A deque allows inserting and deleting elements from both the front and the back, and the doubly linked list provides the necessary operations to support this in constant time.
Approach
The approach is to create a doubly linked list with pointers to the head and tail nodes. Each node will contain a value, a pointer to the previous node, and a pointer to the next node. The MyCircularDeque class will maintain the maximum size (size), current capacity (cap), and the head and tail pointers.
- insertFront(value): Add a new node with
valueat the front of the deque. - insertLast(value): Add a new node with
valueat the end of the deque. - deleteFront(): Remove the node from the front of the deque.
- deleteLast(): Remove the node from the end of the deque.
- getFront(): Return the value of the front node.
- getRear(): Return the value of the rear node.
- isEmpty(): Check if the deque is empty.
- isFull(): Check if the deque is full.
Complexity
-
Time complexity: Each operation runs in constant time, i.e., \(O(1)\), because the deque’s operations involve only pointer updates, regardless of the number of elements.
-
Space complexity: The space complexity is \(O(k)\), where
kis the maximum size of the deque. This is because we need to store up toknodes.
Code
class Node():
def __init__(self, val, prev_node=None, next_node=None):
self.val = val
self.prev = prev_node
self.next = next_node
class MyCircularDeque:
def __init__(self, k: int):
self.head = None
self.tail = None
self.size = k
self.cap = 0
def insertFront(self, value: int) -> bool:
if self.isFull(): return False
curr = self.head
self.head = Node(value, None, curr)
self.head.next = curr
if curr:
curr.prev = self.head
self.cap += 1
if self.cap == 1:
self.tail = self.head
return True
def insertLast(self, value: int) -> bool:
if self.isFull(): return False
curr = self.tail
self.tail = Node(value, curr, None)
self.tail.prev = curr
if curr:
curr.next = self.tail
self.cap += 1
if self.cap == 1:
self.head = self.tail
return True
def deleteFront(self) -> bool:
if self.head is None: return False
curr = self.head
self.head = self.head.next
if self.head:
self.head.prev = None
else:
self.tail = None
curr.next = None
self.cap -= 1
return True
def deleteLast(self) -> bool:
if self.tail is None: return False
curr = self.tail
self.tail = self.tail.prev
if self.tail:
self.tail.next = None
else:
self.head = None
curr.prev = None
self.cap -= 1
return True
def getFront(self) -> int:
if self.cap == 0: return -1
return self.head.val
def getRear(self) -> int:
if self.cap == 0: return -1
return self.tail.val
def isEmpty(self) -> bool:
return self.cap == 0
def isFull(self) -> bool:
return self.cap == self.size
# Your MyCircularDeque object will be instantiated and called as such:
# obj = MyCircularDeque(k)
# param_1 = obj.insertFront(value)
# param_2 = obj.insertLast(value)
# param_3 = obj.deleteFront()
# param_4 = obj.deleteLast()
# param_5 = obj.getFront()
# param_6 = obj.getRear()
# param_7 = obj.isEmpty()
# param_8 = obj.isFull()
Editorial
Approach 1: Linked List
class Node:
def __init__(self, val, next=None, prev=None):
self.val = val
self.next = next
self.prev = prev
class MyCircularDeque:
def __init__(self, k: int):
self.size = 0
self.capacity = k
self.head = None
self.rear = None
def insertFront(self, value: int) -> bool:
if self.isFull():
return False
if self.head is None:
self.head = Node(value, None, None)
self.rear = self.head
else:
newHead = Node(value, self.head, None)
self.head.prev = newHead
self.head = newHead
self.size += 1
return True
def insertLast(self, value: int) -> bool:
if self.isFull():
return False
if self.head is None:
self.head = Node(value, None, None)
self.rear = self.head
else:
self.rear.next = Node(value, None, self.rear)
self.rear = self.rear.next
self.size += 1
return True
def deleteFront(self) -> bool:
if self.isEmpty():
return False
if self.size == 1:
self.head = None
self.rear = None
else:
self.head = self.head.next
self.size -= 1
return True
def deleteLast(self) -> bool:
if self.isEmpty():
return False
if self.size == 1:
self.head = None
self.rear = None
else:
self.rear = self.rear.prev
self.size -= 1
return True
def getFront(self) -> int:
return -1 if self.isEmpty() else self.head.val
def getRear(self) -> int:
return -1 if self.isEmpty() else self.rear.val
def isEmpty(self) -> bool:
return self.size == 0
def isFull(self) -> bool:
return self.size == self.capacity
- time: O(1)
- space: O(n)
Approach 2: Fixed Array with Circular Ordering
class MyCircularDeque:
def __init__(self, k):
self.queue = [0] * k
self.front = 0
self.rear = k - 1
self.size = 0
self.capacity = k
def insertFront(self, value):
if self.isFull():
return False
self.front = (self.front - 1 + self.capacity) % self.capacity
self.queue[self.front] = value
self.size += 1
return True
def insertLast(self, value):
if self.isFull():
return False
self.rear = (self.rear + 1) % self.capacity
self.queue[self.rear] = value
self.size += 1
return True
def deleteFront(self):
if self.isEmpty():
return False
self.front = (self.front + 1) % self.capacity
self.size -= 1
return True
def deleteLast(self):
if self.isEmpty():
return False
self.rear = (self.rear - 1 + self.capacity) % self.capacity
self.size -= 1
return True
def getFront(self):
if self.isEmpty():
return -1
return self.queue[self.front]
def getRear(self):
if self.isEmpty():
return -1
return self.queue[self.rear]
def isEmpty(self):
return self.size == 0
def isFull(self):
return self.size == self.capacity
- time: O(1)
- space: O(k)
