641.design-circular-deque.md

641. Design Circular Deque

We use similar idea from 622. Design Circular Queue to implement this. The key difference is how we initialize the pointer for rear, we initialize it to k - 1 instead of -1, let's take a look at the following example if we still initialize it to -1:

-1, 0, 1    // index
   [_, _]   // values
 r  f
    
insertFront(5) // front = (front - 1 + k) % k
-1, 0, 1
   [_, 5]
 r     f

getRear() // return values[rear] = undefined

As you can see, we cannot get the rear element correctly, the rear is stale in this case, which leads to the wrong result.

The fix could be:

1. Initialize rear = k - 1: Both insertFront() and insertLast() will leave front == rear after the first insert.
2. Update rear = front when size == 1 in insertFront(value)

// We initialize rear to k - 1

-1, 0, 1    // index
   [_, _]   // values
    f  r

insertFront(5) // front = (front - 1 + k) % k
-1, 0, 1
   [_, 5]
       f
       r

getRear() // return values[rear] = 5

Core Thinking: Align on First Insert

After inserting the first element, you must initialize both front and rear to the same index, no matter which end you inserted at, either insertFront() or insertLast() — because that’s the only element in the deque, and we have to ensure getRear() and getFront() can return the correct value.

class MyCircularDeque(private val k: Int) {

    private val values = IntArray(k)
    private var front = 0
    private var rear = k - 1
    private var size = 0

    fun insertFront(value: Int): Boolean {
        if (isFull()) return false
        front = (front - 1 + k) % k
        values[front] = value
        size++
        return true
    }

    fun insertLast(value: Int): Boolean {
        if (isFull()) return false
        rear = (rear + 1) % k
        values[rear] = value
        size++
        return true
    }

    fun deleteFront(): Boolean {
        if (isEmpty()) return false
        front = (front + 1) % k
        size--
        return true
    }

    fun deleteLast(): Boolean {
        if (isEmpty()) return false
        rear = (rear - 1 + k) % k
        size--
        return true
    }

    fun getFront(): Int {
        if (isEmpty()) return -1
        return values[front]
    }

    fun getRear(): Int {
        if (isEmpty()) return -1
        return values[rear]
    }

    fun isEmpty(): Boolean {
        return size == 0
    }

    fun isFull(): Boolean {
        return size == k
    }
}