LeetCode Solutions Blog

Design Circular Deque

Number: 859

Difficulty: Medium

Paid? No

Problem Description

Design a circular double-ended queue (deque) that supports insertion and deletion at both the front and the rear, along with retrieval of the front and rear elements. The implementation must handle wrap-around using a fixed-size circular buffer and return appropriate responses when the deque is full or empty.

Key Insights

Use a fixed-size array to simulate a circular buffer.
Maintain two pointers (front and rear) to track the positions for insertion/deletion.
Use modulo arithmetic for pointer adjustments to create the circular effect.
Track the number of elements to easily determine if the deque is full or empty.
Ensure that operations such as getFront and getRear return -1 when the deque is empty.

Space and Time Complexity

Time Complexity: O(1) for all operations
Space Complexity: O(k), where k is the size of the deque

Solution

The solution employs a circular array as the underlying data structure to represent the deque. Two pointers, front and rear, are used to manage the insertion and deletion from both ends of the deque. When inserting at the front, the front pointer is decremented modulo the capacity; and for insertion at the rear, the element is added at the current rear pointer and then the rear pointer is incremented modulo the capacity. A size counter tracks the current number of elements, easing the detection of full or empty states. Deletion operations adjust the pointers similarly without shifting elements, thereby achieving constant time complexity for all operations.

Code Solutions

class MyCircularDeque:
    def __init__(self, k: int):
        # Initialize the deque with a fixed capacity of k
        self.capacity = k
        self.deque = [0] * k
        self.size = 0
        self.front = 0            # Points to the current front element
        self.rear = 0             # Points to the next insertion position at rear

    def insertFront(self, value: int) -> bool:
        if self.isFull():
            return False
        # Move front pointer backward using modulo arithmetic
        self.front = (self.front - 1 + self.capacity) % self.capacity
        self.deque[self.front] = value
        self.size += 1
        return True

    def insertLast(self, value: int) -> bool:
        if self.isFull():
            return False
        # Insert element at the rear pointer and update it circularly
        self.deque[self.rear] = value
        self.rear = (self.rear + 1) % self.capacity
        self.size += 1
        return True

    def deleteFront(self) -> bool:
        if self.isEmpty():
            return False
        # Move front pointer forward to delete the current front element
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return True

    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False
        # Move rear pointer backward to delete the last element
        self.rear = (self.rear - 1 + self.capacity) % self.capacity
        self.size -= 1
        return True

    def getFront(self) -> int:
        if self.isEmpty():
            return -1
        return self.deque[self.front]

    def getRear(self) -> int:
        if self.isEmpty():
            return -1
        # Since rear pointer indicates next inserting slot, adjust to get last element
        return self.deque[(self.rear - 1 + self.capacity) % self.capacity]

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == self.capacity