Leetcode Daily Question 28/09/2024 - 641. Design Circular Deque

Problem Description:

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

class MyCircularDeque:
  def __init__(self, k: int):
    self.deque = deque(maxlen=k)
    self.k = k
    
  def insertFront(self, value: int) -> bool:
    dq = self.deque
    if not self.isFull():
      dq.appendleft(value)
      return True
    return False
  
  def insertLast(self, value: int) -> bool:
    dq = self.deque
    if not self.isFull():
      dq.append(value)
      return True
    return False
  
  def deleteFront(self):
    dq = self.deque
    if self.isEmpty():
      return False
    dq.popleft()
    return True
  
  def deleteLast(self):
    dq = self.deque
    if self.isEmpty():
      return False
    dq.pop()
    return True
  
  def getFront(self):
    dq = self.deque
    return -1 if self.isEmpty() else dq[0]
  
  def getRear(self):
    dq = self.deque
    return -1 if self.isEmpty() else dq[-1]
  
  def isEmpty(self):
    return not self.deque
  
  def isFull(self):
    return len(self.deque) == self.k

Explanation:

We can solve this by carefully following the instruction.

First we define our deque. Although it is not necessary, we can define a maxlen attribute to the deque to limit its size to k.

For insertFront and insertLast, we check if the deque is full. If it is, we are not allowed to insert, thus returning False.

def __init__(self, k: int):
  self.deque = deque(maxlen=k)
  self.k = k
  
def insertFront(self, value: int) -> bool:
  dq = self.deque
  if not self.isFull():
    dq.appendleft(value)
  	return True
  return False

def insertLast(self, value: int) -> bool:
  dq = self.deque
  if not self.isFull():
    dq.append(value)
    return True
  return False

For deleteFront and deleteLast, we check if the deque is empty. If it is, we cannot delete anything and we return False.

def deleteFront(self):
  dq = self.deque
  if self.isEmpty():
  	return False
  dq.popleft()
  return True

def deleteLast(self):
  dq = self.deque
  if self.isEmpty():
    return False
  dq.pop()
  return True

For getFront, getRear, we check if the deque is empty, if it is, we cannot get a valid element, so we return -1.

def getFront(self):
  dq = self.deque
  return -1 if self.isEmpty() else dq[0]

def getRear(self):
  dq = self.deque
  return -1 if self.isEmpty() else dq[-1]

Lastly, for isEmpty and isFull, we check if the deque is empty or full and return True/False.

def isEmpty(self):
  return not self.deque

def isFull(self):
  return len(self.deque) == len(self.k)

The time complexity is O(1) since for each deque operation, it takes O(1) time.

The space complexity is O(k) since we need to store elements in a deque that has max length = k.

The full solution can be found near the top of the page.