Deque Design Patterns — Sliding Window, Palindrome, Work Stealing

A deque (double-ended queue) supports O(1) insertion and removal from both ends. This makes it versatile for patterns that need access to both the front and back of a sequence.

from collections import deque

d = deque()
d.append(1)       # right end:  [1]
d.appendleft(2)   # left end:   [2, 1]
d.pop()           # right end:  [2]     returns 1
d.popleft()       # left end:   []      returns 2

Pattern 1: Monotonic Deque (Sliding Window Max/Min)

The most important deque pattern in interviews. Maintain a deque where elements are in decreasing order (for max) so the front always holds the current window’s maximum.

Problem: Sliding Window Maximum (LeetCode 239)

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    """
    Find maximum in each sliding window of size k.
    Time: O(n), Space: O(k)
    """
    dq = deque()   # stores indices, values in decreasing order
    result = []

    for i, num in enumerate(nums):
        # Remove elements outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove smaller elements (they'll never be the max)
        while dq and nums[dq[-1]] <= num:
            dq.pop()

        dq.append(i)

        # Window is fully formed when i >= k-1
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

Trace: nums=[1,3,-1,-3,5,3,6,7], k=3

i=0: num=1   dq=[0]         (push 0)
i=1: num=3   dq=[1]         (1<3, pop 0, push 1)
i=2: num=-1  dq=[1,2]       (push 2)    → max=nums[1]=3
i=3: num=-3  dq=[1,2,3]     (push 3)    → max=nums[1]=3
i=4: num=5   dq=[4]         (pop all, push 4) → max=nums[4]=5
i=5: num=3   dq=[4,5]       (push 5)    → max=nums[4]=5
i=6: num=6   dq=[6]         (pop all, push 6) → max=nums[6]=6
i=7: num=7   dq=[7]         (pop all, push 7) → max=nums[7]=7

Result: [3, 3, 5, 5, 6, 7] ✓

Why Monotonic Deque Works

• Front of deque = index of maximum in current window
• When a larger element enters, smaller elements in deque are useless (they will never be the max while the larger element is in the window)
• Elements leave from the front when they fall outside the window

Pattern 2: Palindrome Checking

A deque lets you compare characters from both ends simultaneously.

def is_palindrome_deque(s: str) -> bool:
    """
    Check palindrome using deque.
    Time: O(n), Space: O(n)
    """
    # Clean string: lowercase, alphanumeric only
    d = deque(c.lower() for c in s if c.isalnum())

    while len(d) > 1:
        if d.popleft() != d.pop():
            return False

    return True

Trace: "racecar"

Deque: [r, a, c, e, c, a, r]
Compare r == r ✓  → [a, c, e, c, a]
Compare a == a ✓  → [c, e, c]
Compare c == c ✓  → [e]
Length <= 1 → True ✓

When This Beats Two Pointers

For simple strings, two pointers on an array works fine. But the deque approach shines when:

• Streaming data: Characters arrive one at a time — append to deque, check from both ends
• Partial palindrome: You can stop early and know which characters remain
• Deque already exists: If data is naturally in a deque, avoid converting

Pattern 3: Work Stealing (Parallel Computing)

In parallel computing, each thread has a deque of tasks. The owner pushes and pops from one end (like a stack), while idle threads steal from the other end.

class WorkStealingDeque:
    """
    Simulates work stealing scheduler.
    Owner: push/pop from RIGHT (LIFO for locality)
    Thieves: steal from LEFT (FIFO for load balance)
    """
    def __init__(self, worker_id: int):
        self.id = worker_id
        self.tasks = deque()

    def push_task(self, task):
        """Owner adds task (right end)."""
        self.tasks.append(task)

    def pop_task(self):
        """Owner takes task (right end — LIFO)."""
        if self.tasks:
            return self.tasks.pop()
        return None

    def steal_task(self):
        """Another worker steals (left end — FIFO)."""
        if self.tasks:
            return self.tasks.popleft()
        return None


def simulate_work_stealing(num_workers: int, tasks: list):
    """
    Distribute tasks, then let idle workers steal.
    """
    workers = [WorkStealingDeque(i) for i in range(num_workers)]

    # Distribute tasks round-robin
    for i, task in enumerate(tasks):
        workers[i % num_workers].push_task(task)

    # Process: each worker works its own deque,
    # idle workers steal from busiest
    results = []
    while any(w.tasks for w in workers):
        for w in workers:
            task = w.pop_task()
            if task is None:
                # Steal from another worker
                for other in workers:
                    if other.id != w.id:
                        task = other.steal_task()
                        if task:
                            break
            if task:
                results.append((w.id, task))

    return results

Why Deque for Work Stealing?

End	Used By	Order	Why
Right (back)	Owner	LIFO	Cache locality — recent tasks are warm
Left (front)	Thief	FIFO	Steal oldest (largest) tasks first

This is used in Java’s ForkJoinPool, Go’s goroutine scheduler, and Rust’s Rayon library.

Pattern 4: BFS/DFS Hybrid (0-1 BFS)

When edge weights are only 0 or 1, use a deque instead of a priority queue. Push 0-weight edges to the front, 1-weight edges to the back.

def shortest_path_01(graph: dict, start: int, end: int) -> int:
    """
    Shortest path with 0/1 edge weights using deque (0-1 BFS).
    Time: O(V + E), Space: O(V)
    """
    dist = {start: 0}
    dq = deque([start])

    while dq:
        node = dq.popleft()

        if node == end:
            return dist[node]

        for neighbor, weight in graph[node]:
            new_dist = dist[node] + weight
            if neighbor not in dist or new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                if weight == 0:
                    dq.appendleft(neighbor)  # front (high priority)
                else:
                    dq.append(neighbor)       # back (normal)

    return -1  # unreachable

Trace

Graph: 0 →(1)→ 1, 0 →(0)→ 2, 2 →(1)→ 3, 1 →(0)→ 3

Start: 0, End: 3

dq=[0]          dist={0:0}
Pop 0:
  → 1 (w=1)    dq=[1]       dist={0:0, 1:1}    (append)
  → 2 (w=0)    dq=[2,1]     dist={0:0, 1:1, 2:0}  (appendleft!)
Pop 2:
  → 3 (w=1)    dq=[1,3]     dist={..., 3:1}
Pop 1:
  → 3 (w=0)    dq=[3,3]     dist={..., 3:1}  (1+0=1, not better)
Pop 3:
  return 1 ✓

When 0-1 BFS Beats Dijkstra

Algorithm	Time	Works For
Dijkstra	O((V+E) log V)	Any non-negative weights
0-1 BFS	O(V + E)	Only 0 and 1 weights

Complexity Summary

Pattern	Time	Space	Key Deque Feature Used
Monotonic Deque	O(n)	O(k)	Pop from both ends
Palindrome Check	O(n)	O(n)	Compare front and back
Work Stealing	O(tasks)	O(tasks)	LIFO one end, FIFO other
0-1 BFS	O(V+E)	O(V)	Appendleft for priority

When to Use This Pattern

• Sliding window problems: Monotonic deque whenever you need min/max in a window
• Two-end processing: When you need to consume data from both ends
• Priority without heap: 0-1 BFS replaces priority queue for binary weights
• Parallel algorithms: Work stealing is fundamental to modern schedulers

Related Problems

• Sliding Window Maximum — deep dive on this specific problem
• Shortest Path in Binary Matrix — BFS on grids
• Queues and Deques Deep Dive — deque internals