119. Design Circular Deque

🔗 LeetCode Problem: 641. Design Circular Deque
📊 Difficulty: Medium
🏷️ Topics: Array, Deque, Design

Problem Statement

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

Example:

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]

Explanation:
MyCircularDeque myCircularDeque = new MyCircularDeque(3);
myCircularDeque.insertLast(1);  // return True
myCircularDeque.insertLast(2);  // return True
myCircularDeque.insertFront(3); // return True
myCircularDeque.insertFront(4); // return False (full)
myCircularDeque.getRear();      // return 2
myCircularDeque.isFull();       // return True
myCircularDeque.deleteLast();   // return True
myCircularDeque.insertFront(4); // return True
myCircularDeque.getFront();     // return 4

Constraints: - 1 <= k <= 1000 - 0 <= value <= 1000 - At most 2000 calls will be made to operations.

---

🌟 Understanding the Problem

What is a Deque?

Deque = Double-Ended Queue

Regular Queue:
  Add at rear → [1, 2, 3] → Remove from front
                F     R

Deque:
  Add/Remove from BOTH ends!

  ← insertFront        insertLast →
     deleteFront →  ← deleteLast

      [1, 2, 3]
       F     R

Why "Circular"?

Array wraps around to reuse space:

Linear:  [_, _, 3, 4, 5] → Can't reuse front
          wasted!

Circular: Elements wrap around
     [0]
  [4]   [1]
  [3]   [2]

When we reach end, we go back to start!

---

💡 Building Intuition

Question 1: How Do We Track Elements?

We need TWO pointers:
  - front: Points to first element
  - rear: Points to last element

Example with [3, 1, 2]:
  data = [1, 2, 3]
            R  F

  Order: 3 (front) → 1 → 2 (rear)
  Reading from front to rear gives us: 3, 1, 2

Question 2: How to Move Pointers?

Moving Forward (right):

(index + 1) % capacity

Examples with capacity = 5:
  Index 0 → (0 + 1) % 5 = 1
  Index 4 → (4 + 1) % 5 = 0  ← Wraps to start!

Moving Backward (left):

(index - 1 + capacity) % capacity

Why +capacity? To handle negative numbers!

Examples with capacity = 5:
  Index 2 → (2 - 1 + 5) % 5 = 1
  Index 0 → (0 - 1 + 5) % 5 = 4  ← Wraps to end!

Question 3: How to Know When Full or Empty?

Both full and empty can have front == rear!

Empty: front = 0, rear = -1, count = 0
  [_, _, _]

Full: front = 2, rear = 1, count = 3
  [1, 2, 3]
      R  F

Solution: Track count!
  count == 0 → empty
  count == capacity → full

Question 4: Why rear = -1 Initially?

Starting with rear = -1 is smart!

When we insertLast(5):
  rear = (rear + 1) % capacity
  rear = (-1 + 1) % 3 = 0
  data[0] = 5

Works perfectly without special case!

If we started with rear = 0:
  Need special if-else for first element
  More complex!

Question 5: Why Update Opposite Pointer on First Element?

When deque is EMPTY and we insert FIRST element:

insertFront(5):
  front moves to index 2
  data[2] = 5
  count = 1

  But rear is still -1!
  Problem: rear should also point to element!

  Solution: if (count == 1) rear = front;
  Now: front = 2, rear = 2 ✓
  Both point to the only element!

Same for insertLast:
  rear moves to index 0
  data[0] = 5
  count = 1

  But front is still 0 (which is correct!)
  Solution: if (count == 1) front = rear;

The Rule:

When inserting the FIRST element (count becomes 1):
  Both pointers must point to that element!

  insertFront: Update rear = front
  insertLast: Update front = rear

---

🎯 Approach 1: List with Shifts (Not Circular)

The Idea

Use ArrayList, shift elements when needed.
Simple but inefficient.

Implementation

class MyCircularDeque {
    private List<Integer> data;
    private int capacity;

    public MyCircularDeque(int k) {
        data = new ArrayList<>();
        capacity = k;
    }

    public boolean insertFront(int value) {
        if (data.size() == capacity) return false;
        data.add(0, value);  // O(n) - shifts all!
        return true;
    }

    public boolean insertLast(int value) {
        if (data.size() == capacity) return false;
        data.add(value);  // O(1)
        return true;
    }

    public boolean deleteFront() {
        if (data.isEmpty()) return false;
        data.remove(0);  // O(n) - shifts all!
        return true;
    }

    public boolean deleteLast() {
        if (data.isEmpty()) return false;
        data.remove(data.size() - 1);  // O(1)
        return true;
    }

    public int getFront() {
        return data.isEmpty() ? -1 : data.get(0);
    }

    public int getRear() {
        return data.isEmpty() ? -1 : data.get(data.size() - 1);
    }

    public boolean isEmpty() {
        return data.isEmpty();
    }

    public boolean isFull() {
        return data.size() == capacity;
    }
}

Complexity Analysis

⏰ Time: - insertFront(): O(n) - Shifts elements - deleteFront(): O(n) - Shifts elements - insertLast(): O(1) - deleteLast(): O(1) - Others: O(1)

💾 Space: O(k)

The Problem

Front operations are O(n)!
Not truly circular - doesn't reuse space

---

✅ Approach 2: Circular Array with Two Pointers (Optimal)

The Idea

Use circular array with front and rear pointers
Both can move forward and backward
Track count for empty/full detection

Implementation

class MyCircularDeque {
    private int[] data;
    private int front;
    private int rear;
    private int count;
    private int capacity;

    public MyCircularDeque(int k) {
        data = new int[k];
        front = 0;
        rear = -1;
        count = 0;
        capacity = k;
    }

    public boolean insertFront(int value) {
        if (isFull()) return false;

        // Move front backward
        front = (front - 1 + capacity) % capacity;
        data[front] = value;
        count++;

        // If first element, rear should also point to it
        if (count == 1) {
            rear = front;
        }

        return true;
    }

    public boolean insertLast(int value) {
        if (isFull()) return false;

        // Move rear forward
        rear = (rear + 1) % capacity;
        data[rear] = value;
        count++;

        // If first element, front should also point to it
        if (count == 1) {
            front = rear;
        }

        return true;
    }

    public boolean deleteFront() {
        if (isEmpty()) return false;

        // Move front forward
        front = (front + 1) % capacity;
        count--;

        return true;
    }

    public boolean deleteLast() {
        if (isEmpty()) return false;

        // Move rear backward
        rear = (rear - 1 + capacity) % capacity;
        count--;

        return true;
    }

    public int getFront() {
        return isEmpty() ? -1 : data[front];
    }

    public int getRear() {
        return isEmpty() ? -1 : data[rear];
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public boolean isFull() {
        return count == capacity;
    }
}

Complexity Analysis

⏰ Time: All operations O(1)

💾 Space: O(k)

Detailed Dry Run

═══════════════════════════════════════════════════════════
Operations: MyCircularDeque(3), insertLast(1), insertLast(2),
            insertFront(3), insertFront(4), getRear(), isFull(),
            deleteLast(), insertFront(4), getFront()
═══════════════════════════════════════════════════════════

Initialization: MyCircularDeque(3)

  data = [_, _, _]  (size 3)
  front = 0
  rear = -1
  count = 0
  capacity = 3

═══════════════════════════════════════════════════════════
Operation: insertLast(1)
═══════════════════════════════════════════════════════════

Step 1: Check if full
  isFull()? count == capacity?
  0 == 3? NO

Step 2: Move rear forward
  rear = (rear + 1) % capacity
  rear = (-1 + 1) % 3 = 0

Step 3: Insert value
  data[0] = 1

Step 4: Increment count
  count = 1

Step 5: If first element, update front
  count == 1? YES
  front = rear = 0

State:
  data = [1, _, _]
         F/R
  front = 0, rear = 0, count = 1

Return: true ✓

Explanation:
  First element inserted at index 0
  Both front and rear point to it
  This is correct - only one element!

═══════════════════════════════════════════════════════════
Operation: insertLast(2)
═══════════════════════════════════════════════════════════

Step 1: Check if full
  1 == 3? NO

Step 2: Move rear forward
  rear = (0 + 1) % 3 = 1

Step 3: Insert value
  data[1] = 2

Step 4: Increment count
  count = 2

Step 5: If first element, update front
  count == 1? NO
  Skip

State:
  data = [1, 2, _]
         F  R
  front = 0, rear = 1, count = 2

Return: true ✓

Deque order: 1 → 2

═══════════════════════════════════════════════════════════
Operation: insertFront(3)
═══════════════════════════════════════════════════════════

Step 1: Check if full
  2 == 3? NO

Step 2: Move front backward
  front = (front - 1 + capacity) % capacity
  front = (0 - 1 + 3) % 3
  front = 2 % 3 = 2

Step 3: Insert value
  data[2] = 3

Step 4: Increment count
  count = 3

Step 5: If first element, update rear
  count == 1? NO
  Skip

State:
  data = [1, 2, 3]
            R  F
  front = 2, rear = 1, count = 3

Deque order: 3 → 1 → 2
  Front: 3 (at index 2)
  Rear: 2 (at index 1)

Return: true ✓

Visual of circular arrangement:
     [0]=1
  [2]=3 [1]=2
     F     R

Reading from front: 3, then 0, then 1
  → Elements: 3, 1, 2 ✓

═══════════════════════════════════════════════════════════
Operation: insertFront(4)
═══════════════════════════════════════════════════════════

Step 1: Check if full
  isFull()? count == capacity?
  3 == 3? YES

Return: false ✓

Deque is FULL - cannot insert!

═══════════════════════════════════════════════════════════
Operation: getRear()
═══════════════════════════════════════════════════════════

Check if empty: NO

Return: data[rear] = data[1] = 2 ✓

═══════════════════════════════════════════════════════════
Operation: isFull()
═══════════════════════════════════════════════════════════

Check: count == capacity?
  3 == 3? YES

Return: true ✓

═══════════════════════════════════════════════════════════
Operation: deleteLast()
═══════════════════════════════════════════════════════════

Step 1: Check if empty
  isEmpty()? count == 0?
  3 == 0? NO

Step 2: Move rear backward
  rear = (rear - 1 + capacity) % capacity
  rear = (1 - 1 + 3) % 3
  rear = 3 % 3 = 0

Step 3: Decrement count
  count = 2

State:
  data = [1, 2, 3]
         R     F
  front = 2, rear = 0, count = 2

Deque order: 3 → 1
  Front: 3 (at index 2)
  Rear: 1 (at index 0)
  Element 2 is logically removed

Return: true ✓

Explanation:
  Rear moved backward from 1 to 0
  Element at index 1 (value 2) is now outside deque
  We didn't erase it, just moved pointer

═══════════════════════════════════════════════════════════
Operation: insertFront(4)
═══════════════════════════════════════════════════════════

Step 1: Check if full
  2 == 3? NO

Step 2: Move front backward
  front = (2 - 1 + 3) % 3 = 1

Step 3: Insert value
  data[1] = 4

Step 4: Increment count
  count = 3

Step 5: If first element, update rear
  count == 1? NO

State:
  data = [1, 4, 3]
         R  F
  front = 1, rear = 0, count = 3

Deque order: 4 → 3 → 1
  Front: 4 (at index 1)
  Rear: 1 (at index 0)

Return: true ✓

Explanation:
  We overwrote index 1 (old value 2)
  Now it has value 4
  Space reused perfectly!

═══════════════════════════════════════════════════════════
Operation: getFront()
═══════════════════════════════════════════════════════════

Check if empty: NO

Return: data[front] = data[1] = 4 ✓

Final state:
  data = [1, 4, 3]
         R  F

Deque: 4 → 3 → 1

---

📊 Approach Comparison

┌─────────────────────────────────────────────────────────┐
│               Approach 1         Approach 2             │
│               (List)             (Circular Array)       │
├─────────────────────────────────────────────────────────┤
│ Strategy      Shift elements     Two pointers + modulo  │
│                                                          │
│ insertFront   O(n)               O(1) ✓                 │
│ insertLast    O(1)               O(1) ✓                 │
│ deleteFront   O(n)               O(1) ✓                 │
│ deleteLast    O(1)               O(1) ✓                 │
│                                                          │
│ Space         O(k)               O(k)                   │
│                                                          │
│ Circular      No                 Yes ✓                  │
│ behavior                                                 │
│                                                          │
│ Best for      Never              Always! ✓              │
└─────────────────────────────────────────────────────────┘

Which Approach to Use?

Approach 2 (Circular Array) is the ONLY correct solution!

Why Approach 2:
  ✓ All operations O(1)
  ✓ True circular behavior
  ✓ Efficient bidirectional access
  ✓ Space reuse via wraparound
  ✓ This is the expected solution

---

🧪 Edge Cases

Edge Case 1: Single Element Deque

MyCircularDeque(1)

insertFront(1) → true, front=0, rear=0
insertLast(2) → false (full)
getFront() → 1
getRear() → 1
deleteFront() → true
isEmpty() → true ✓

Edge Case 2: Insert First via insertFront

MyCircularDeque(3)

insertFront(5):
  front = (0 - 1 + 3) % 3 = 2
  data[2] = 5
  count = 1
  rear = front = 2  ← Both point to index 2!

Correct! ✓

Edge Case 3: Insert First via insertLast

MyCircularDeque(3)

insertLast(5):
  rear = (-1 + 1) % 3 = 0
  data[0] = 5
  count = 1
  front = rear = 0  ← Both point to index 0!

Correct! ✓

Edge Case 4: Wraparound

MyCircularDeque(3)

Multiple operations cause wraparound:
  front and rear wrap around multiple times
  Modulo handles all correctly ✓

---

⚠️ Common Mistakes

Mistake 1: Wrong backward formula

// ❌ WRONG - Negative modulo issues
front = (front - 1) % capacity;
// Can give negative results!

// ✓ CORRECT - Add capacity first
front = (front - 1 + capacity) % capacity;

Mistake 2: Not updating opposite pointer on first element

// ❌ WRONG
public boolean insertFront(int value) {
    front = (front - 1 + capacity) % capacity;
    data[front] = value;
    count++;
    // Forgot: if (count == 1) rear = front;
}

// ✓ CORRECT
if (count == 1) {
    rear = front;  // Both must point to first element!
}

Mistake 3: Using separate empty/full flags

// ❌ WRONG - Unnecessary
boolean isEmpty, isFull;

// ✓ CORRECT - Use count
// count == 0 → empty
// count == capacity → full

Mistake 4: Starting rear at 0

// ❌ WRONG - Causes extra complexity
rear = 0;
// Need special if-else in insertLast

// ✓ CORRECT - Start at -1
rear = -1;
// Works smoothly with (rear + 1) % capacity

---

🎯 Pattern Recognition

When you see:

- "double-ended queue"
- "deque"
- "insert/delete from both ends"
- "circular buffer"

Think:
  "Circular array with bidirectional pointers"
  "Modulo for wraparound"
  "Count for empty/full check"

Similar Problems: - Design Circular Queue (LC 622) - LRU Cache (LC 146) - Sliding Window Maximum (LC 239)

---

📝 Quick Revision Notes

🎯 Core Concept

Circular deque allows insert/delete from BOTH ends. Use array with front/rear pointers. rear = -1 initially. Forward: (i+1)%k, Backward: (i-1+k)%k. Update opposite pointer when inserting first element.

⚡ Quick Implementation

class MyCircularDeque {
  int[] a;
  int capacity;
  int front = 0;
  int rear = -1;
  int size = 0;

  // Differences between CircularQueue and CircularDequeue
  // 1. When moving backward, modulo calculation.
  // 2. If first element, front and rear assignments. Only single size deque (count = 1) is the edge case in which we need to point both front and rear on the same element. Rest of the cases can be tackled normally.

  public MyCircularDeque(int k) {
    a = new int[k];
    capacity = k;    
  }

  public boolean isEmpty() {
    return size == 0;      
  }

  public boolean isFull() {
    return size == capacity;      
  }

  public int getFront() {
    return isEmpty() ? -1 : a[front]; 
  }

  public int getRear() {
    return isEmpty() ? -1 : a[rear];
  }

  public boolean insertLast(int value) {
    if(isFull()) {
      return false;
    }

    rear = (rear + 1) % capacity;
    a[rear] = value;
    size++;

    // If first element, front should also point to it
    if (size == 1) {
      front = rear;
    }    

    return true;
  }

  public boolean insertFront(int value) {
    if(isFull()) {
      return false;
    }

    front = (front - 1 + capacity) % capacity;
    a[front] = value;
    size++;

    // If first element, rear should also point to it
    if (size == 1) {
      rear = front;
    }

    return true;
  }

  public boolean deleteFront() {
    if(isEmpty()) {
      return false;
    }

    front = (front + 1) % capacity;
    size--;

    return true;
  }

  public boolean deleteLast() {
    if(isEmpty()) {
      return false;
    }

    rear = (rear - 1 + capacity) % capacity;
    size--;

    return true;
  }
}

class Solution {
  public static void main(String[] args) {
    MyCircularDeque m = new MyCircularDeque(3);
    System.out.println(m.insertLast(1));
    System.out.println(m.insertLast(2));
    System.out.println(m.insertFront(3));
    System.out.println(m.insertFront(4));
    System.out.println(m.getRear());
    System.out.println(m.isFull());
    System.out.println(m.deleteLast());
    System.out.println(m.insertFront(4));
    System.out.println(m.getFront());
  }
}

🔑 Key Insights

• Pattern: Bidirectional circular buffer
• Initial values: front=0, rear=-1
• Forward: (index + 1) % capacity
• Backward: (index - 1 + capacity) % capacity
• First element: Update opposite pointer
• Empty check: count == 0
• Full check: count == capacity
• Time: All operations O(1) ✓
• Space: O(k)

🎪 Memory Aid

"Two-ended queue, two-way movement!"
"Backward? Add capacity before modulo!"
"First element? Both pointers point to it!" ✨

⚠️ Don't Forget

• Use rear = -1 initially
• Add capacity when going backward: (i - 1 + capacity) % k
• Update opposite pointer when count becomes 1
• Use count for empty/full checks
• All operations must be O(1)

---

Happy practicing! 🎯