Double Ended Queue Deque in DSA Python - Time & Space Complexity

Time Complexity: Double Ended Queue Deque

O(n) for front insert/remove, O(1) for rear insert/remove

Understanding Time Complexity

We want to understand how fast operations on a double ended queue (deque) run as the number of items grows.

Specifically, how does adding or removing items from either end affect the time it takes?

Scenario Under Consideration

Analyze the time complexity of the following deque operations.

class Deque:
    def __init__(self):
        self.items = []

    def add_front(self, item):
        self.items.insert(0, item)

    def add_rear(self, item):
        self.items.append(item)

    def remove_front(self):
        return self.items.pop(0)

    def remove_rear(self):
        return self.items.pop()

This code shows basic add and remove operations at both ends of a deque using a Python list.

Identify Repeating Operations

Look at the operations that repeat when we add or remove items.

• Primary operation: Inserting or removing at the front uses list insert(0, item) or pop(0).
• How many times: Each add or remove at front shifts all other elements, so it repeats work proportional to the number of items.
• Adding or removing at the rear uses append() or pop() which work directly at the end without shifting.

How Execution Grows With Input

Adding or removing at the rear stays fast no matter how many items there are.

But adding or removing at the front takes longer as the list grows because all items must move.

Input Size (n)	Approx. Operations for front insert/pop	Approx. Operations for rear append/pop
10	10 shifts	1 operation
100	100 shifts	1 operation
1000	1000 shifts	1 operation

Pattern observation: Front operations grow linearly with n, rear operations stay constant.

Final Time Complexity

Time Complexity: O(n) for front insert/remove, O(1) for rear insert/remove

This means adding or removing at the front takes longer as the deque grows, but rear operations stay fast.

Common Mistake

[X] Wrong: "All deque operations are always fast and take the same time."

[OK] Correct: Using a list, front operations shift all items, so they take longer as size grows, unlike rear operations.

Interview Connect

Understanding how different deque operations scale helps you choose the right data structure and explain your choices clearly in interviews.

Self-Check

"What if we used a linked list instead of a Python list? How would the time complexity of front insert and remove change?"

Practice

1. What is a deque in Python's collections module?

easy

A. A list that automatically sorts elements when inserted

B. A queue that only allows insertion at the rear and removal from the front

C. A stack that only allows insertion and removal from the top

D. A double-ended queue allowing insertion and removal from both ends

Solution

1. Step 1: Understand the deque concept

   A deque is a data structure that supports adding and removing elements from both the front and the back efficiently.

2. Step 2: Compare with other data structures

   Unlike a queue or stack, deque allows operations on both ends, not just one end.

3. Final Answer:

   A double-ended queue allowing insertion and removal from both ends -> Option D

4. Quick Check:

   Deque = double-ended queue [OK]

Hint: Remember: deque means double-ended queue [OK]

Common Mistakes:

• Confusing deque with stack or queue
• Thinking deque only works like a queue
• Assuming deque sorts elements automatically

2. Which of the following is the correct way to import and create an empty deque in Python?

easy

A. import collections\nd = collections.deque[]

B. from collections import deque\nd = deque()

C. from collections import Deque\nd = Deque()

D. import deque\nd = deque()

Solution

1. Step 1: Check the correct import statement

   The deque class is in the collections module and must be imported as from collections import deque.

2. Step 2: Verify deque creation syntax

   Creating an empty deque is done by calling deque() with parentheses, not brackets.

3. Final Answer:

   from collections import deque\nd = deque() -> Option B

4. Quick Check:

   Correct import and empty deque creation [OK]

Hint: Use 'from collections import deque' and call deque() [OK]

Common Mistakes:

• Using uppercase 'Deque' instead of 'deque'
• Trying to import deque directly without collections
• Using square brackets [] instead of parentheses ()

3. What will be the output of the following code?

from collections import deque
d = deque([1, 2, 3])
d.appendleft(0)
d.append(4)
print(list(d))

medium

A. [4, 1, 2, 3, 0]

B. [1, 2, 3, 0, 4]

C. [0, 1, 2, 3, 4]

D. [1, 2, 3, 4, 0]

Solution

1. Step 1: Trace deque initialization and appendleft

   Deque starts as [1, 2, 3]. After appendleft(0), it becomes [0, 1, 2, 3].

2. Step 2: Trace append operation

   After append(4), 4 is added to the right end, making deque [0, 1, 2, 3, 4].

3. Final Answer:

   [0, 1, 2, 3, 4] -> Option C

4. Quick Check:

   appendleft adds front, append adds end [OK]

Hint: appendleft adds front, append adds end [OK]

Common Mistakes:

• Confusing appendleft with append
• Assuming append adds to front
• Not converting deque to list before printing

4. Find the error in the following code snippet:

from collections import deque
d = deque()
d.appendleft(1)
d.append(2)
d.pop()
d.pop()
d.pop()

medium

A. Calling pop() on an empty deque causes an IndexError

B. appendleft() is not a valid method for deque

C. deque() cannot be initialized empty

D. append() requires two arguments

Solution

1. Step 1: Analyze deque operations

   Deque starts empty, then 1 is added to front, 2 to end. After two pops, deque is empty.

2. Step 2: Identify error on third pop

   The third pop tries to remove from empty deque, causing IndexError.

3. Final Answer:

   Calling pop() on an empty deque causes an IndexError -> Option A

4. Quick Check:

   pop on empty deque throws error [OK]

Hint: pop() on empty deque causes error [OK]

Common Mistakes:

• Thinking appendleft() is invalid
• Assuming deque can't be empty
• Believing append() needs two arguments

5. You have a deque initialized as d = deque([10, 20, 30, 40]). You want to rotate it so that the element 30 becomes the first element. Which code snippet achieves this correctly?

hard

A. d.rotate(-2)

B. d.rotate(2)

C. d.rotate(-3)

D. d.rotate(3)

Solution

1. Step 1: Understand deque rotation

   Positive rotate moves elements to the right; negative rotate moves to the left.

2. Step 2: Calculate rotation to bring 30 to front

   30 is at index 2. Rotating left by 2 (rotate(-2)) moves 30 to front.

3. Final Answer:

   d.rotate(-2) -> Option A

4. Quick Check:

   Negative rotate shifts left, bringing 30 front [OK]

Hint: Negative rotate shifts left; positive shifts right [OK]

Common Mistakes:

• Using positive rotate instead of negative
• Confusing rotation direction
• Not counting index positions correctly