Queue & Deque — The Complete Guide

function bfs(root: TreeNode | null): number[][] {
  if (!root) return [];
  const result: number[][] = [];
  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const levelSize = queue.length; // snapshot current level size
    const level: number[] = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      level.push(node.val);

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(level);
  }

  return result;
}
// When to use: level-order traversal, zigzag traversal,
// right side view, average of levels, minimum depth

function shortestPath(grid: number[][], start: [number, number], end: [number, number]): number {
  const rows = grid.length, cols = grid[0].length;
  const queue: [number, number, number][] = [[start[0], start[1], 0]]; // [row, col, dist]
  const visited = new Set<string>();
  visited.add(`${start[0]},${start[1]}`);

  const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];

  while (queue.length > 0) {
    const [r, c, dist] = queue.shift()!;

    if (r === end[0] && c === end[1]) return dist;

    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      const key = `${nr},${nc}`;

      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
          && grid[nr][nc] === 0 && !visited.has(key)) {
        visited.add(key);
        queue.push([nr, nc, dist + 1]);
      }
    }
  }

  return -1; // unreachable
}
// When to use: shortest path in maze, word ladder,
// minimum knight moves, open the lock

function multiSourceBFS(grid: number[][]): number[][] {
  const rows = grid.length, cols = grid[0].length;
  const dist = Array.from({ length: rows }, () => new Array(cols).fill(-1));
  const queue: [number, number][] = [];

  // Enqueue ALL sources at once
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === SOURCE) {
        queue.push([r, c]);
        dist[r][c] = 0;
      }
    }
  }

  const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];

  while (queue.length > 0) {
    const [r, c] = queue.shift()!;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && dist[nr][nc] === -1) {
        dist[nr][nc] = dist[r][c] + 1;
        queue.push([nr, nc]);
      }
    }
  }

  return dist;
}
// When to use: rotting oranges, walls and gates,
// 01 matrix (nearest 0), map of highest peak

function slidingWindowMax(nums: number[], k: number): number[] {
  const deque: number[] = []; // indices in decreasing value order
  const result: number[] = [];

  for (let i = 0; i < nums.length; i++) {
    // Expire: remove indices outside the window from front
    while (deque.length > 0 && deque[0] <= i - k) {
      deque.shift();
    }

    // Maintain monotonic order: remove smaller from back
    while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }

    deque.push(i);

    // Window is full — record the max (front of deque)
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}
// For sliding window MINIMUM: flip the comparison to >=
// When to use: sliding window maximum, shortest subarray with sum >= k,
// constrained subsequence sum, longest continuous subarray with abs diff <= limit

function orangesRotting(grid: number[][]): number {
  const rows = grid.length, cols = grid[0].length;
  const queue: [number, number][] = [];
  let fresh = 0;

  // Enqueue ALL rotten oranges as sources
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r, c]);
      if (grid[r][c] === 1) fresh++;
    }
  }

  if (fresh === 0) return 0;

  const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
  let minutes = 0;

  while (queue.length > 0 && fresh > 0) {
    const size = queue.length;
    minutes++;

    for (let i = 0; i < size; i++) {
      const [r, c] = queue.shift()!;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
          grid[nr][nc] = 2; // rot it
          fresh--;
          queue.push([nr, nc]);
        }
      }
    }
  }

  return fresh === 0 ? minutes : -1;
}
// Time: O(rows × cols) — each cell processed at most once
// Space: O(rows × cols) — queue can hold all cells
// Key: ALL rotten oranges start in the queue at time 0.
// BFS expands one "ring" per minute — exactly like ripples in a pond.

function zeroOneBFS(graph: Map<number, [number, number][]>, start: number, n: number): number[] {
  const dist = new Array(n).fill(Infinity);
  dist[start] = 0;
  const deque: number[] = [start];

  while (deque.length > 0) {
    const u = deque.shift()!;

    for (const [v, weight] of graph.get(u) ?? []) {
      const newDist = dist[u] + weight;
      if (newDist < dist[v]) {
        dist[v] = newDist;
        if (weight === 0) {
          deque.unshift(v); // 0-weight → push to FRONT
        } else {
          deque.push(v);    // 1-weight → push to BACK
        }
      }
    }
  }

  return dist;
}
// Time: O(V + E) — same as regular BFS
// Space: O(V) for distance array + deque
// Key: 0-weight edges go to front (processed immediately),
// 1-weight edges go to back (processed later).
// This maintains the BFS invariant: deque is sorted by distance.

function maxResult(nums: number[], k: number): number {
  const n = nums.length;
  const dp = new Array(n).fill(0);
  dp[0] = nums[0];
  const deque: number[] = [0]; // indices, decreasing dp values

  for (let i = 1; i < n; i++) {
    // Expire: remove indices outside the jump window
    while (deque.length > 0 && deque[0] < i - k) {
      deque.shift();
    }

    // dp[i] = nums[i] + max(dp[j]) for j in [i-k, i-1]
    dp[i] = nums[i] + dp[deque[0]];

    // Maintain decreasing order: remove smaller dp values from back
    while (deque.length > 0 && dp[deque[deque.length - 1]] <= dp[i]) {
      deque.pop();
    }

    deque.push(i);
  }

  return dp[n - 1];
}
// Time: O(n) — each index pushed/popped at most once
// Space: O(n) for dp array, O(k) for deque
// Key: the deque maintains the maximum dp value within the jump window.
// This is the "DP + monotonic deque" pattern — very common in hard problems.

Tree:
        3
       / \
      9   20
         /  \
        15   7

queue = [3]

Level 0: levelSize = 1
  Dequeue 3 → level = [3]
  Enqueue children: 9, 20
  queue = [9, 20]
  result = [[3]]

Level 1: levelSize = 2
  Dequeue 9 → level = [9]    (no children)
  Dequeue 20 → level = [9, 20]
  Enqueue children: 15, 7
  queue = [15, 7]
  result = [[3], [9, 20]]

Level 2: levelSize = 2
  Dequeue 15 → level = [15]  (no children)
  Dequeue 7 → level = [15, 7] (no children)
  queue = []
  result = [[3], [9, 20], [15, 7]]

Queue empty → done.

Answer: [[3], [9, 20], [15, 7]]

Key: The "levelSize = queue.length" snapshot at the start of each
iteration tells you exactly how many nodes belong to the current level.
Everything enqueued during this iteration belongs to the NEXT level.

Grid:        2  1  1
             1  1  0
             0  1  1

Initial: queue = [(0,0)], fresh = 6

Minute 1: process (0,0)
  Rot (0,1) and (1,0)
  queue = [(0,1), (1,0)], fresh = 4
  Grid:  2  2  1
         2  1  0
         0  1  1

Minute 2: process (0,1) and (1,0)
  (0,1) rots (0,2) and (1,1)
  (1,0) has no fresh neighbors (already rotten or wall)
  queue = [(0,2), (1,1)], fresh = 2
  Grid:  2  2  2
         2  2  0
         0  1  1

Minute 3: process (0,2) and (1,1)
  (0,2) has no fresh neighbors
  (1,1) rots (2,1)
  queue = [(2,1)], fresh = 1
  Grid:  2  2  2
         2  2  0
         0  2  1

Minute 4: process (2,1)
  (2,1) rots (2,2)
  queue = [(2,2)], fresh = 0
  Grid:  2  2  2
         2  2  0
         0  2  2

fresh = 0 → done!

Answer: 4 minutes

Key: ALL rotten oranges start in the queue simultaneously.
Each "minute" is one BFS level. The answer is the number of levels.

Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
deque = [] (stores indices), result = []

i=0: num=1
  deque empty → push 0
  deque = [0]                    (values: [1])
  window not full yet

i=1: num=3
  nums[0]=1 ≤ 3 → pop 0 from back
  push 1
  deque = [1]                    (values: [3])
  window not full yet

i=2: num=-1
  nums[1]=3 > -1 → keep
  push 2
  deque = [1, 2]                 (values: [3, -1])
  window full → result.push(nums[1]) = 3
  result = [3]

i=3: num=-3
  deque[0]=1, 1 > 3-3=0 → not expired
  nums[2]=-1 > -3 → keep
  push 3
  deque = [1, 2, 3]             (values: [3, -1, -3])
  result.push(nums[1]) = 3
  result = [3, 3]

i=4: num=5
  deque[0]=1, 1 ≤ 4-3=1 → EXPIRE, shift
  nums[2]=-1 ≤ 5 → pop from back
  nums[3]=-3 ≤ 5 → pop from back
  push 4
  deque = [4]                    (values: [5])
  result.push(nums[4]) = 5
  result = [3, 3, 5]

i=5: num=3
  nums[4]=5 > 3 → keep
  push 5
  deque = [4, 5]                 (values: [5, 3])
  result.push(nums[4]) = 5
  result = [3, 3, 5, 5]

i=6: num=6
  nums[5]=3 ≤ 6 → pop from back
  nums[4]=5 ≤ 6 → pop from back
  push 6
  deque = [6]                    (values: [6])
  result.push(nums[6]) = 6
  result = [3, 3, 5, 5, 6]

i=7: num=7
  nums[6]=6 ≤ 7 → pop from back
  push 7
  deque = [7]                    (values: [7])
  result.push(nums[7]) = 7
  result = [3, 3, 5, 5, 6, 7]

Answer: [3, 3, 5, 5, 6, 7]

Key: The deque always holds indices in DECREASING value order.
Front = current window max. Back = where new elements enter.
Smaller elements are removed from back (they can never be max).
Expired elements are removed from front (they left the window).

Does the problem ask for shortest path or minimum steps?
├── YES → Are all edge weights equal?
│         ├── YES → BFS with a Queue (Template 2)
│         └── NO  → Are weights only 0 and 1?
│                   ├── YES → 0-1 BFS with a Deque
│                   └── NO  → Dijkstra with a Heap (not a queue problem)
└── NO  → Does the problem ask for level-by-level processing?
          ├── YES → BFS Level-Order with a Queue (Template 1)
          └── NO  → Does the problem involve multiple starting points expanding outward?
                    ├── YES → Multi-Source BFS (Template 3)
                    └── NO  → Does the problem need min/max in a sliding window?
                              ├── YES → Monotonic Deque (Template 4)
                              └── NO  → Does a DP recurrence need max/min over a range of previous states?
                                        ├── YES → DP + Monotonic Deque
                                        └── NO  → Does the problem involve FIFO processing or simulation?
                                                  ├── YES → Basic Queue
                                                  └── NO  → Queue/Deque probably isn't the right pattern
                                                            → Consider Stack, Heap, or Two Pointers