LeetCode 641: Design Circular Deque Solution in Python – A Step-by-Step Guide

What Is LeetCode 641: Design Circular Deque?

In LeetCode 641: Design Circular Deque, you’re tasked with implementing a MyCircularDeque class with a fixed capacity k and these methods:

• insertFront(value): Add an element to the front.
• insertLast(value): Add an element to the rear.
• deleteFront(): Remove the front element.
• deleteLast(): Remove the rear element.
• getFront(): Return the front element (-1 if empty).
• getRear(): Return the rear element (-1 if empty).
• isEmpty(): Check if deque is empty.
• isFull(): Check if deque is full.

Unlike a regular deque, this one is circular—when the rear or front reaches the end, it wraps around to the start if space is available. For example, with k=3, you can add 1, 2, 3, remove from the front, and add 4 at the front. This problem tests your ability to manage a fixed-size, double-ended queue with wrap-around logic.

Problem Statement

• Input:
• k: Integer capacity (1 ≤ k ≤ 1000).
• Method calls with values (0 ≤ value ≤ 1000).
• Output: A MyCircularDeque class implementing the methods.
• Rules:
• Fixed size k.
• Circular: Front/rear wrap around when space allows.
• Return booleans for success, -1 for empty access.

Constraints

• 1 ≤ k ≤ 1000.
• 0 ≤ value ≤ 1000.
• Up to 2000 method calls.

Examples

• Input:
• ["MyCircularDeque","insertLast","insertLast","insertFront","insertFront","getRear","isFull","deleteLast","insertFront","getFront"]
• [[3],[1],[2],[3],[4],[],[],[],[4],[]]
• Output: [null,true,true,true,false,2,true,true,true,4]
• Init k=3, add 1, 2, 3 (full), 4 fails, remove 2, add 4 at front.
• Input:
• ["MyCircularDeque","insertFront","deleteLast","getFront"]
• [[1],[1],[],[]]
• Output: [null,true,true,-1]
• Init k=1, add 1, remove, empty.

These examples set the deque—let’s solve it!

Understanding the Problem: Designing a Circular Deque

To solve LeetCode 641: Design Circular Deque in Python, we need to create a class that manages a fixed-size deque where elements can be added or removed from both ends, wrapping around circularly when space permits. A naive approach—using a list with shifting—would be O(n) for inserts/deletes, inefficient for k ≤ 1000. We’ll use:

• Best Solution (Array-Based with Pointers): O(1) time per operation, O(k) space—fast and space-efficient.
• Alternative Solution (Doubly Linked List): O(1) time per operation, O(k) space—flexible but memory-heavy.

Let’s start with the array-based solution, breaking it down for beginners.

Best Solution: Array-Based Circular Deque with Pointers

Why This Is the Best Solution

The array-based circular deque with pointers is the top choice for LeetCode 641 because it’s efficient—O(1) time for all operations with O(k) space—and uses a fixed array with front and rear pointers to manage the circular structure, minimizing memory overhead. It fits constraints (k ≤ 1000) and is straightforward once you grasp the wrap-around logic. It’s like a circular conveyor belt with precise slot tracking!

How It Works

Think of this as a circular slot manager:

• Step 1: Initialize:
• Array of size k, front/rear pointers, size counter.
• Step 2: Insert Front:
• If not full, decrement front (mod k), add value, increment size.
• Step 3: Insert Last:
• If not full, add at rear, increment rear (mod k), increment size.
• Step 4: Delete Front:
• If not empty, increment front (mod k), decrement size.
• Step 5: Delete Last:
• If not empty, decrement rear (mod k), decrement size.
• Step 6: Get Front/Rear:
• Return values at pointers (-1 if empty).
• Step 7: Check Empty/Full:
• Empty: size = 0, Full: size = k.

It’s like a deque ring—spin and manage!

Step-by-Step Example

Example: k=3, Operations: insertLast(1), insertLast(2), insertFront(3), deleteLast(), insertFront(4)

• Step 1: Init:
• deque = [None, None, None], front = 0, rear = 0, size = 0.
• Step 2: insertLast(1):
• deque[0] = 1, rear = 1, size = 1.
• Step 3: insertLast(2):
• deque[1] = 2, rear = 2, size = 2.
• Step 4: insertFront(3):
• front = 2 (mod 3), deque[2] = 3, size = 3 (full).
• Step 5: deleteLast():
• rear = 1, size = 2, deque = [1, 2, 3] (2 removed logically).
• Step 6: insertFront(4):
• front = 1 (mod 3), deque[1] = 4, size = 3, deque = [1, 4, 3].
• Output: [null, true, true, true, true, true].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class MyCircularDeque:
    def __init__(self, k: int):
        # Step 1: Initialize array and pointers
        self.k = k
        self.deque = [None] * k
        self.front = 0  # Index of front element
        self.rear = 0   # Index where next rear goes
        self.size = 0   # Current number of elements

    def insertFront(self, value: int) -> bool:
        # Step 2: Add to front if not full
        if self.isFull():
            return False
        self.front = (self.front - 1) % self.k  # Wrap around
        self.deque[self.front] = value
        self.size += 1
        return True

    def insertLast(self, value: int) -> bool:
        # Step 3: Add to rear if not full
        if self.isFull():
            return False
        self.deque[self.rear] = value
        self.rear = (self.rear + 1) % self.k  # Wrap around
        self.size += 1
        return True

    def deleteFront(self) -> bool:
        # Step 4: Remove from front if not empty
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.k  # Wrap around
        self.size -= 1
        return True

    def deleteLast(self) -> bool:
        # Step 5: Remove from rear if not empty
        if self.isEmpty():
            return False
        self.rear = (self.rear - 1) % self.k  # Wrap around
        self.size -= 1
        return True

    def getFront(self) -> int:
        # Step 6: Return front element
        if self.isEmpty():
            return -1
        return self.deque[self.front]

    def getRear(self) -> int:
        # Step 7: Return rear element
        if self.isEmpty():
            return -1
        return self.deque[(self.rear - 1) % self.k]

    def isEmpty(self) -> bool:
        # Step 8: Check if empty
        return self.size == 0

    def isFull(self) -> bool:
        # Step 9: Check if full
        return self.size == self.k

• Lines 4-8: Init: Array of size k, pointers at 0, size tracker.
• Lines 11-16: insertFront: Move front back, add value.
• Lines 19-24: insertLast: Add at rear, move forward.
• Lines 27-31: deleteFront: Move front forward.
• Lines 34-38: deleteLast: Move rear back.
• Lines 41-44: getFront: Return front value.
• Lines 47-50: getRear: Return rear value.
• Lines 53-55: isEmpty: Size = 0.
• Lines 58-60: isFull: Size = k.
• Time Complexity: O(1) per operation.
• Space Complexity: O(k)—fixed array.

This is like a deque spinner—fast and tight!

Alternative Solution: Doubly Linked List-Based Circular Deque

Why an Alternative Approach?

The doubly linked list-based approach uses nodes with prev/next pointers—O(1) time per operation, O(k) space. It’s more flexible, dynamically linking elements, but uses extra memory for pointers and isn’t cache-friendly. It’s like a chain of slots looping around!

How It Works

Picture this as a linked loop:

• Step 1: Init with sentinel node for circularity.
• Step 2: Insert Front: Add node after sentinel.
• Step 3: Insert Last: Add node before sentinel.
• Step 4: Delete Front/Last: Remove nodes, adjust links.
• Step 5: Get Front/Rear: Access head/tail values.
• Step 6: Check Empty/Full: Use size counter.

It’s like a deque chain—flexible but heavy!

Step-by-Step Example

Example: Same as above

• Init: Sentinel, size = 0, k = 3.
• InsertLast(1): Sentinel ↔ 1, size = 1.
• InsertLast(2): Sentinel ↔ 1 ↔ 2, size = 2.
• InsertFront(3): Sentinel ↔ 3 ↔ 1 ↔ 2, size = 3.
• DeleteLast(): Sentinel ↔ 3 ↔ 1, size = 2.
• InsertFront(4): Sentinel ↔ 4 ↔ 3 ↔ 1, size = 3.

Code for Linked List Approach

class Node:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

class MyCircularDeque:
    def __init__(self, k: int):
        self.k = k
        self.size = 0
        self.sentinel = Node(0)
        self.sentinel.prev = self.sentinel.next = self.sentinel

    def insertFront(self, value: int) -> bool:
        if self.isFull():
            return False
        node = Node(value)
        node.next = self.sentinel.next
        node.prev = self.sentinel
        self.sentinel.next.prev = node
        self.sentinel.next = node
        self.size += 1
        return True

    def insertLast(self, value: int) -> bool:
        if self.isFull():
            return False
        node = Node(value)
        node.prev = self.sentinel.prev
        node.next = self.sentinel
        self.sentinel.prev.next = node
        self.sentinel.prev = node
        self.size += 1
        return True

    def deleteFront(self) -> bool:
        if self.isEmpty():
            return False
        self.sentinel.next = self.sentinel.next.next
        self.sentinel.next.prev = self.sentinel
        self.size -= 1
        return True

    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False
        self.sentinel.prev = self.sentinel.prev.prev
        self.sentinel.prev.next = self.sentinel
        self.size -= 1
        return True

    def getFront(self) -> int:
        return -1 if self.isEmpty() else self.sentinel.next.value

    def getRear(self) -> int:
        return -1 if self.isEmpty() else self.sentinel.prev.value

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

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

• Lines 8-12: Init with sentinel for circularity.
• Lines 15-22: insertFront: Add after sentinel.
• Lines 25-32: insertLast: Add before sentinel.
• Time Complexity: O(1) per operation.
• Space Complexity: O(k)—nodes.

It’s a linked deque—flexible but bulkier!

Comparing the Two Solutions

• Array-Based (Best):
• Pros: O(1) time, O(k) space, cache-friendly.
• Cons: Fixed structure.
• Linked List (Alternative):
• Pros: O(1) time, O(k) space, dynamic.
• Cons: More memory, less efficient.

Array-based wins for efficiency.

Additional Examples and Edge Cases

• Input: k=1, insertFront(1), insertLast(2)
• Output: [true, false].
• Input: k=1, deleteFront()
• Output: [false].

Both handle these well.

Complexity Breakdown

• Array-Based: Time O(1), Space O(k).
• Linked List: Time O(1), Space O(k).

Array-based is optimal.

Key Takeaways

• Array-Based: Pointer precision—smart!
• Linked List: Node flexibility—clear!
• Deques: Circular is fun.
• Python Tip: Arrays rock—see Python Basics.

Final Thoughts: Design That Deque

LeetCode 641: Design Circular Deque in Python is a cool data structure challenge. Array-based with pointers offers speed and simplicity, while linked lists add flexibility. Want more? Try LeetCode 622: Design Circular Queue or LeetCode 146: LRU Cache. Ready to spin? Head to Solve LeetCode 641 on LeetCode and design that deque today!