> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Queue Pattern

> Master FIFO operations for BFS, scheduling, and stream processing

<img className="block rounded-lg" src="https://mintcdn.com/devweeekends/8SzFxu49daVetHjN/images/dsa-techniques/12-queue.svg?fit=max&auto=format&n=8SzFxu49daVetHjN&q=85&s=0ac1904c6093e9b03cfe6fa4965ffd9f" alt="Queue Pattern" width="1080" height="1080" data-path="images/dsa-techniques/12-queue.svg" />

## What is Queue?

**Queue** is a FIFO (First In, First Out) data structure where elements are added at the back and removed from the front. Think of a real-world queue at a coffee shop: the first person in line is the first person served. No cutting, no skipping.

In algorithm problems, queues are the workhorse behind **Breadth-First Search (BFS)** -- processing nodes level by level guarantees shortest-path discovery in unweighted graphs. They also power sliding-window maximums (via a deque), task scheduling, and stream processing problems.

**Key operations and their complexity:**

* `enqueue` (push to back): O(1)
* `dequeue` (pop from front): O(1)
* `peek` (view front element): O(1)

In Python, always use `collections.deque` instead of a plain list for queue operations -- `list.pop(0)` is O(n) because it shifts all elements, while `deque.popleft()` is O(1).

## Pattern Recognition Cheatsheet

<Tip>
  **These exact problem-statement keywords should make you reach for a queue (or deque) within 30 seconds.** A queue is the workhorse for level-order processing and stream windows.

  | Keyword / Shape in Problem                           | Queue Variant to Use                          |
  | ---------------------------------------------------- | --------------------------------------------- |
  | "BFS", "shortest path in unweighted graph"           | Standard FIFO queue of nodes                  |
  | "level order", "level by level", "for each level"    | Queue plus `level_size = len(queue)` snapshot |
  | "minimum number of steps/moves", "fewest operations" | BFS with a queue (steps == levels)            |
  | "rotting oranges", "walls and gates", "01 matrix"    | Multi-source BFS (enqueue all sources first)  |
  | "rate limit window", "requests in the last N ms"     | Queue of timestamps with eviction             |
  | "moving average", "sum of last K elements"           | Fixed-size queue plus running sum             |
  | "sliding window maximum / minimum"                   | Monotonic deque of indices                    |
  | "first non-repeating character in a stream"          | Queue plus frequency map                      |
  | "task scheduler", "round robin", "fair queue"        | Priority queue or multi-level queue           |
  | "design hit counter"                                 | Deque of (timestamp, count) buckets           |
  | "design recent counter (LC 933)"                     | Deque, evict timestamps older than t - 3000   |

  **Mental shortcut:** if the problem talks about *order of arrival* or *processing nearest-first*, it is a queue. If it talks about *the maximum/minimum within a window of size K*, it is a monotonic deque. If it talks about *priority / urgency*, it is a heap, not a queue.
</Tip>

## Reusable Template Code

Three skeletons cover the vast majority of queue problems.

<CodeGroup>
  ```python Python theme={null}
  from collections import deque

  # Skeleton 1: BFS level-order traversal
  def bfs_levels(root):
      if not root: return []
      queue = deque([root])
      levels = []
      while queue:
          level_size = len(queue)            # SNAPSHOT before adding next level
          level = []
          for _ in range(level_size):
              node = queue.popleft()
              level.append(node.val)
              if node.left:  queue.append(node.left)
              if node.right: queue.append(node.right)
          levels.append(level)
      return levels

  # Skeleton 2: Sliding window maximum (monotonic deque)
  def sliding_max(nums, k):
      dq = deque()                           # stores INDICES, values decreasing
      result = []
      for i, x in enumerate(nums):
          while dq and dq[0] <= i - k:       # evict expired
              dq.popleft()
          while dq and nums[dq[-1]] < x:     # evict smaller (irrelevant) tail
              dq.pop()
          dq.append(i)
          if i >= k - 1:
              result.append(nums[dq[0]])
      return result

  # Skeleton 3: Sliding-time-window counter (rate limit, recent calls)
  class RecentCounter:
      def __init__(self):
          self.q = deque()
      def ping(self, t):
          self.q.append(t)
          while self.q[0] < t - 3000:        # evict timestamps older than 3 seconds
              self.q.popleft()
          return len(self.q)
  ```

  ```java Java theme={null}
  // Skeleton 1: BFS level-order
  public List<List<Integer>> bfsLevels(TreeNode root) {
      List<List<Integer>> result = new ArrayList<>();
      if (root == null) return result;
      Deque<TreeNode> queue = new ArrayDeque<>();
      queue.offer(root);
      while (!queue.isEmpty()) {
          int levelSize = queue.size();          // SNAPSHOT
          List<Integer> level = new ArrayList<>();
          for (int i = 0; i < levelSize; i++) {
              TreeNode node = queue.poll();
              level.add(node.val);
              if (node.left  != null) queue.offer(node.left);
              if (node.right != null) queue.offer(node.right);
          }
          result.add(level);
      }
      return result;
  }

  // Skeleton 2: Sliding window maximum
  public int[] slidingMax(int[] nums, int k) {
      int n = nums.length;
      int[] result = new int[n - k + 1];
      Deque<Integer> dq = new ArrayDeque<>();    // stores indices
      for (int i = 0; i < n; i++) {
          while (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
          while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast();
          dq.offerLast(i);
          if (i >= k - 1) result[i - k + 1] = nums[dq.peekFirst()];
      }
      return result;
  }
  ```
</CodeGroup>

<Warning>
  **Python performance trap:** `list.pop(0)` is O(n) because it shifts every remaining element left. For BFS over a tree with thousands of nodes, this turns your O(n) algorithm into O(n^2). **Always** use `collections.deque` with `popleft()` -- it is O(1).

  **Java idiom:** prefer `ArrayDeque` over `LinkedList`. Both implement `Deque` but `ArrayDeque` has better cache locality, no per-node allocation, and is roughly 2x faster in practice. The only reason to use `LinkedList` is if you specifically need `null` elements (which `ArrayDeque` rejects).
</Warning>

## When to Use

<CardGroup cols={2}>
  <Card title="BFS" icon="sitemap">
    Level-order traversal, shortest path
  </Card>

  <Card title="Scheduling" icon="calendar">
    Task queues, round-robin
  </Card>

  <Card title="Sliding Window" icon="window-restore">
    With deque for O(1) operations
  </Card>

  <Card title="Streaming Data" icon="wave-square">
    Moving averages, recent items
  </Card>
</CardGroup>

## Pattern Variations

### 1. Implement Queue using Stacks

This is a classic design question that tests your understanding of FIFO vs LIFO. The trick: use two stacks. One is the "inbox" where new elements land; the other is the "outbox" from which we serve elements. When the outbox is empty, pour everything from inbox into outbox -- this reverses the order, giving us FIFO behavior.

**Amortized complexity:** Each element is moved from inbox to outbox exactly once, so all operations are **amortized O(1)**, even though a single `pop` might trigger an O(n) transfer.

**Interview tip:** Be ready to explain the amortized analysis. The key argument: every element goes through at most 2 pushes and 2 pops across both stacks during its entire lifetime.

<CodeGroup>
  ```python Python theme={null}
  class MyQueue:
      """FIFO queue built from two LIFO stacks.
      
      Analogy: Think of two tubes of tennis balls. You load balls into
      tube A (inbox). When you need to serve, flip tube A upside down
      into tube B (outbox) -- the bottom ball (first in) is now on top.
      """
      
      def __init__(self):
          self.inbox = []   # New elements land here
          self.outbox = []  # Elements ready to be served (reversed order)
      
      def push(self, x):
          self.inbox.append(x)
      
      def pop(self):
          self._transfer()         # Ensure outbox has elements
          return self.outbox.pop() # Serve from the "front" of the queue
      
      def peek(self):
          self._transfer()
          return self.outbox[-1]   # Look at front without removing
      
      def empty(self):
          return not self.inbox and not self.outbox
      
      def _transfer(self):
          """Move all elements from inbox to outbox (reversing order).
          Only transfer when outbox is empty to preserve FIFO ordering."""
          if not self.outbox:
              while self.inbox:
                  self.outbox.append(self.inbox.pop())
  ```

  ```java Java theme={null}
  class MyQueue {
      // FIFO queue using two LIFO stacks
      private Deque<Integer> inbox;
      private Deque<Integer> outbox;
      
      public MyQueue() {
          inbox = new ArrayDeque<>();  // For push
          outbox = new ArrayDeque<>(); // For pop/peek
      }
      
      public void push(int x) {
          inbox.push(x);
      }
      
      public int pop() {
          transfer();
          return outbox.pop();
      }
      
      public int peek() {
          transfer();
          return outbox.peek();
      }
      
      public boolean empty() {
          return inbox.isEmpty() && outbox.isEmpty();
      }
      
      private void transfer() {
          if (outbox.isEmpty()) {
              while (!inbox.isEmpty()) {
                  outbox.push(inbox.pop());
              }
          }
      }
  }
  ```

  ```cpp C++ theme={null}
  class MyQueue {
      // FIFO queue using two LIFO stacks
  private:
      stack<int> inbox;  // For push
      stack<int> outbox; // For pop/peek
      
      void transfer() {
          if (outbox.empty()) {
              while (!inbox.empty()) {
                  outbox.push(inbox.top());
                  inbox.pop();
              }
          }
      }
      
  public:
      void push(int x) {
          inbox.push(x);
      }
      
      int pop() {
          transfer();
          int val = outbox.top();
          outbox.pop();
          return val;
      }
      
      int peek() {
          transfer();
          return outbox.top();
      }
      
      bool empty() {
          return inbox.empty() && outbox.empty();
      }
  };
  ```
</CodeGroup>

### 2. Moving Average from Data Stream

<CodeGroup>
  ```python Python theme={null}
  from collections import deque

  class MovingAverage:
      """Calculate moving average of last n elements"""
      
      def __init__(self, size):
          self.size = size
          self.queue = deque()
          self.total = 0
      
      def next(self, val):
          self.queue.append(val)
          self.total += val
          
          if len(self.queue) > self.size:
              self.total -= self.queue.popleft()
          
          return self.total / len(self.queue)
  ```

  ```java Java theme={null}
  class MovingAverage {
      // Calculate moving average of last n elements
      private int size;
      private Queue<Integer> queue;
      private double total;
      
      public MovingAverage(int size) {
          this.size = size;
          this.queue = new LinkedList<>();
          this.total = 0;
      }
      
      public double next(int val) {
          queue.offer(val);
          total += val;
          
          if (queue.size() > size) {
              total -= queue.poll();
          }
          
          return total / queue.size();
      }
  }
  ```

  ```cpp C++ theme={null}
  class MovingAverage {
      // Calculate moving average of last n elements
  private:
      int size;
      queue<int> q;
      double total;
      
  public:
      MovingAverage(int size) : size(size), total(0) {}
      
      double next(int val) {
          q.push(val);
          total += val;
          
          if (q.size() > size) {
              total -= q.front();
              q.pop();
          }
          
          return total / q.size();
      }
  };
  ```
</CodeGroup>

### 3. Sliding Window Maximum (Monotonic Deque)

Finding the maximum in every window of size k is O(n \* k) with brute force. A monotonic deque brings this down to O(n) by maintaining a decreasing sequence of *candidate maximums*. The front of the deque is always the current window's maximum. We remove from the front when it slides out of the window, and we remove from the back when a new element makes older, smaller elements irrelevant.

**Complexity:** O(n) time (each element is added and removed from the deque at most once), O(k) space for the deque.

**Why a deque and not a regular queue?** We need to remove from *both ends*: the front (expired indices) and the back (smaller elements).

<CodeGroup>
  ```python Python theme={null}
  from collections import deque

  def max_sliding_window(nums, k):
      """Return the maximum value in each sliding window of size k.
      
      Example: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
      Windows:  [1,3,-1] [3,-1,-3] [-1,-3,5] [-3,5,3] [5,3,6] [3,6,7]
      Maxima:     3        3         5         5        6        7
      """
      result = []
      dq = deque()  # Stores indices; values at these indices are in decreasing order
      
      for i in range(len(nums)):
          # 1. Remove indices that have fallen out of the window
          while dq and dq[0] <= i - k:
              dq.popleft()
          
          # 2. Remove indices whose values are smaller than the new element
          #    (they can never be the maximum while the new element is in the window)
          while dq and nums[dq[-1]] < nums[i]:
              dq.pop()
          
          dq.append(i)
          
          # 3. Record the maximum once the first full window is formed
          if i >= k - 1:
              result.append(nums[dq[0]])  # Front of deque is the max
      
      return result
  ```

  ```java Java theme={null}
  public int[] maxSlidingWindow(int[] nums, int k) {
      // Maximum in each window of size k
      int[] result = new int[nums.length - k + 1];
      Deque<Integer> dq = new ArrayDeque<>(); // Store indices
      
      for (int i = 0; i < nums.length; i++) {
          // Remove indices out of window
          while (!dq.isEmpty() && dq.peekFirst() <= i - k) {
              dq.pollFirst();
          }
          
          // Remove smaller elements
          while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
              dq.pollLast();
          }
          
          dq.offerLast(i);
          
          // Add to result once window is formed
          if (i >= k - 1) {
              result[i - k + 1] = nums[dq.peekFirst()];
          }
      }
      
      return result;
  }
  ```

  ```cpp C++ theme={null}
  vector<int> maxSlidingWindow(vector<int>& nums, int k) {
      // Maximum in each window of size k
      vector<int> result;
      deque<int> dq; // Store indices
      
      for (int i = 0; i < nums.size(); i++) {
          // Remove indices out of window
          while (!dq.empty() && dq.front() <= i - k) {
              dq.pop_front();
          }
          
          // Remove smaller elements
          while (!dq.empty() && nums[dq.back()] < nums[i]) {
              dq.pop_back();
          }
          
          dq.push_back(i);
          
          // Add to result once window is formed
          if (i >= k - 1) {
              result.push_back(nums[dq.front()]);
          }
      }
      
      return result;
  }
  ```
</CodeGroup>

### 4. BFS Level Order Traversal

BFS with a queue is the natural way to process a tree (or graph) level by level. The critical trick is snapshotting the queue size at the start of each level -- this tells you how many nodes belong to the current level before you start adding children from the next level.

**Complexity:** O(n) time, O(w) space where w is the maximum width of the tree (up to n/2 for a complete binary tree).

**Interview tip:** Many problems are disguised BFS: "minimum moves," "rotting oranges" (multi-source BFS), "shortest path in unweighted graph." If you see "minimum steps" or "level by level," think queue immediately.

<CodeGroup>
  ```python Python theme={null}
  from collections import deque

  def level_order(root):
      """Binary tree level order traversal.
      
      Example tree:        3
                          / \
                         9   20
                            /  \
                           15   7
      Result: [[3], [9, 20], [15, 7]]
      """
      if not root:
          return []
      
      result = []
      queue = deque([root])
      
      while queue:
          level = []
          level_size = len(queue)  # Snapshot: how many nodes in this level
          
          for _ in range(level_size):
              node = queue.popleft()
              level.append(node.val)
              
              # Enqueue children (they belong to the next level)
              if node.left:
                  queue.append(node.left)
              if node.right:
                  queue.append(node.right)
          
          result.append(level)
      
      return result
  ```

  ```java Java theme={null}
  public List<List<Integer>> levelOrder(TreeNode root) {
      // Binary tree level order traversal
      List<List<Integer>> result = new ArrayList<>();
      if (root == null) return result;
      
      Queue<TreeNode> queue = new LinkedList<>();
      queue.offer(root);
      
      while (!queue.isEmpty()) {
          List<Integer> level = new ArrayList<>();
          int levelSize = queue.size();
          
          for (int i = 0; i < levelSize; i++) {
              TreeNode node = queue.poll();
              level.add(node.val);
              
              if (node.left != null) queue.offer(node.left);
              if (node.right != null) queue.offer(node.right);
          }
          
          result.add(level);
      }
      
      return result;
  }
  ```

  ```cpp C++ theme={null}
  vector<vector<int>> levelOrder(TreeNode* root) {
      // Binary tree level order traversal
      vector<vector<int>> result;
      if (root == nullptr) return result;
      
      queue<TreeNode*> q;
      q.push(root);
      
      while (!q.empty()) {
          vector<int> level;
          int levelSize = q.size();
          
          for (int i = 0; i < levelSize; i++) {
              TreeNode* node = q.front();
              q.pop();
              level.push_back(node->val);
              
              if (node->left) q.push(node->left);
              if (node->right) q.push(node->right);
          }
          
          result.push_back(level);
      }
      
      return result;
  }
  ```
</CodeGroup>

## Classic Problems

| Problem            | Pattern                | Key Insight                          | Complexity            |
| ------------------ | ---------------------- | ------------------------------------ | --------------------- |
| BFS Traversal      | Standard queue         | Process level by level               | O(n) time, O(w) space |
| Sliding Window Max | Monotonic deque        | Keep decreasing order                | O(n) time, O(k) space |
| Queue via Stacks   | Two stacks             | Amortized O(1) operations            | Amortized O(1) per op |
| Moving Average     | Fixed-size queue       | Running sum optimization             | O(1) per call         |
| Task Scheduler     | Priority queue + queue | Cool down management                 | O(n) time             |
| Rotting Oranges    | Multi-source BFS       | Start from all rotten simultaneously | O(m \* n) time        |

## Worked LeetCode Problems: Brute Force vs Optimized

Four canonical problems cover the queue interview surface. Each one teaches a distinct sub-pattern.

### LC 102: Binary Tree Level Order Traversal (Medium)

**Problem.** Return the values of a binary tree level by level, top to bottom.

**Brute force.** Use DFS, tag each node with its depth, group by depth at the end. Works but is O(n) extra space and obscures the level-by-level intent.

**Optimized BFS (O(n) time, O(w) space where w is max width).** Queue with the level-size snapshot trick.

```python theme={null}
from collections import deque
def level_order(root):
    if not root: return []
    out, q = [], deque([root])
    while q:
        level_size = len(q)             # SNAPSHOT -- this is the trick
        level = []
        for _ in range(level_size):
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        out.append(level)
    return out
```

**The level-size snapshot insight.** Without taking `len(q)` *before* the inner loop, you cannot tell where the current level ends and the next begins -- adding children to the queue mid-loop confuses the boundary. Snapshot first, drain that many, then move on.

### LC 622: Design Circular Queue (Medium)

**Problem.** Implement a fixed-size circular queue with `enQueue`, `deQueue`, `Front`, `Rear`, `isEmpty`, `isFull` -- all O(1).

**Brute force.** Linked list with explicit head and tail. Works but allocates per insert and lacks cache locality.

**Optimized -- ring buffer with two pointers.** Fixed array, `head` and `tail` indices, wrap with modulo. Track `count` (or leave one slot unused) to distinguish empty from full.

```python theme={null}
class MyCircularQueue:
    def __init__(self, k):
        self.q = [0] * k
        self.head = 0
        self.count = 0
        self.k = k
    def enQueue(self, value):
        if self.count == self.k: return False
        tail = (self.head + self.count) % self.k
        self.q[tail] = value
        self.count += 1
        return True
    def deQueue(self):
        if self.count == 0: return False
        self.head = (self.head + 1) % self.k
        self.count -= 1
        return True
    def Front(self): return -1 if self.count == 0 else self.q[self.head]
    def Rear(self):  return -1 if self.count == 0 else self.q[(self.head + self.count - 1) % self.k]
    def isEmpty(self): return self.count == 0
    def isFull(self):  return self.count == self.k
```

**Real-world tie-in.** Linux's `sk_buff` ring, Java's `ArrayBlockingQueue`, the LMAX Disruptor, and audio playback buffers all use this exact pattern. The ring buffer is one of the most-used data structures in systems programming.

### LC 933: Number of Recent Calls (Easy)

**Problem.** Each call to `ping(t)` adds a request at time `t`. Return the number of pings in the last 3000 ms (inclusive).

**Brute force.** Store all timestamps in a list; on each `ping`, scan backward to count recent ones. O(n) per call.

**Optimized -- deque with eviction.** Append the new timestamp; pop from the front anything older than `t - 3000`; return the deque size.

```python theme={null}
from collections import deque
class RecentCounter:
    def __init__(self):
        self.q = deque()
    def ping(self, t):
        self.q.append(t)
        while self.q[0] < t - 3000:
            self.q.popleft()
        return len(self.q)
```

**Why amortized O(1).** Each timestamp is appended once and popped at most once across its lifetime. The while-loop looks scary but contributes at most O(n) total across all calls.

### LC 239: Sliding Window Maximum (Hard) -- Monotonic Deque

**Problem.** Given `nums` and window size `k`, return the maximum of every contiguous window of size `k`.

**Brute force (O(n\*k)).** For each window, scan and find the max. Times out on large inputs.

**Optimized monotonic deque (O(n)).** Maintain a deque of indices where the values are strictly decreasing. The front is always the current window's max. On each step: evict expired indices from the front, evict smaller indices from the back, append the new index.

```python theme={null}
from collections import deque
def max_sliding_window(nums, k):
    dq = deque()
    out = []
    for i, x in enumerate(nums):
        while dq and dq[0] <= i - k:        # expired
            dq.popleft()
        while dq and nums[dq[-1]] < x:      # smaller than new -- they cannot be max
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            out.append(nums[dq[0]])
        # NB: wrote dq[0] <= i - k (uses unicode-safe ascii), and nums[dq[-1]] < x
    return out
```

**Why a deque, not a heap?** A max-heap solves it in O(n log k) but cannot remove arbitrary expired indices in O(1) -- you would need lazy deletion. The monotonic deque achieves O(n) amortized, strictly better.

## Caveats and Traps

<Warning>
  **Bugs Every Queue Problem Hides:**

  1. **`list.pop(0)` is O(n) in Python.** Iterating a BFS over 100k nodes with `list.pop(0)` quietly turns your O(n) algorithm into O(n^2). Always `from collections import deque` and use `popleft()`.
  2. **Thread safety for concurrent producers.** A bare `deque` or `ArrayDeque` is not thread-safe. Multiple producers calling `append`/`offer` simultaneously can corrupt the queue. Use `queue.Queue` (Python) or `LinkedBlockingQueue` / `ConcurrentLinkedQueue` (Java) when crossing thread boundaries.
  3. **Forgetting the level-size snapshot in BFS.** Without `level_size = len(queue)` taken *before* the inner loop, you cannot tell where one level ends and the next begins. You will conflate levels and break level-by-level problems.
  4. **Storing nodes by value when you need parent/depth context.** Push tuples like `(node, depth)` or `(node, parent)` into the queue when the algorithm needs more than the node itself.
  5. **Using a regular queue when you need ordering by priority.** "Process the most urgent task first" means heap, not queue. FIFO is for arrival order; heap is for priority order.
  6. **Forgetting to mark visited in graph BFS.** Without a `visited` set, you re-enqueue the same nodes, blow up memory, and may never terminate on cyclic graphs.
  7. **In sliding window max, comparing `dq[0]` to a stale index.** Always evict from the front *before* doing the front-equals-max read. Otherwise you read a stale max from outside the window.
</Warning>

<Tip>
  **Solutions and Idioms -- Paired with the Caveats Above:**

  1. **Always `from collections import deque`** at the top of any BFS or sliding-window solution. Make it muscle memory.
  2. **Choose the right concurrent queue:** for producer-consumer, `LinkedBlockingQueue` (bounded) or `ConcurrentLinkedQueue` (unbounded, lock-free). For Python multi-threading, `queue.Queue`. For asyncio, `asyncio.Queue`.
  3. **Level-by-level BFS template:** outer `while queue:` plus inner `for _ in range(len(queue)):`. Internalize this pattern -- it solves Level Order, Min Depth, Right Side View, Word Ladder, and Rotting Oranges with the same skeleton.
  4. **Tuple-payload trick:** `queue.append((node, depth, path))` -- carry whatever context you need on the queue itself rather than maintaining parallel structures.
  5. **When to upgrade to heap:** if any node has a "cost" or "weight" that determines processing order, switch to `heapq.heappush`/`heappop`. BFS becomes Dijkstra.
  6. **Visited-set discipline:** `visited.add(start)` before the loop, `visited.add(neighbor)` BEFORE enqueuing (not when dequeuing), to prevent the same neighbor being added by two different parents.
  7. **Sliding-deque mantra:** "Evict expired front, evict useless tail, append, then read." Always in that order.
</Tip>

## Curated LeetCode Practice List

The classic queue problem set, grouped by difficulty.

### Easy

| #    | Problem                                                                                               | Pattern Variant                |
| ---- | ----------------------------------------------------------------------------------------------------- | ------------------------------ |
| 933  | [Number of Recent Calls](https://leetcode.com/problems/number-of-recent-calls/)                       | Time-window deque              |
| 232  | [Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/)           | Two-stack amortization         |
| 225  | [Implement Stack using Queues](https://leetcode.com/problems/implement-stack-using-queues/)           | Reverse trick                  |
| 346  | [Moving Average from Stream](https://leetcode.com/problems/moving-average-from-data-stream/)          | Fixed-size queue + running sum |
| 1700 | [Students Unable to Eat Lunch](https://leetcode.com/problems/number-of-students-unable-to-eat-lunch/) | Direct queue simulation        |

### Medium

| #    | Problem                                                                                     | Pattern Variant            |
| ---- | ------------------------------------------------------------------------------------------- | -------------------------- |
| 102  | [Binary Tree Level Order](https://leetcode.com/problems/binary-tree-level-order-traversal/) | BFS with level snapshot    |
| 199  | [Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/)   | Last node of each level    |
| 994  | [Rotting Oranges](https://leetcode.com/problems/rotting-oranges/)                           | Multi-source BFS           |
| 542  | [01 Matrix](https://leetcode.com/problems/01-matrix/)                                       | Multi-source BFS distance  |
| 622  | [Design Circular Queue](https://leetcode.com/problems/design-circular-queue/)               | Ring buffer                |
| 641  | [Design Circular Deque](https://leetcode.com/problems/design-circular-deque/)               | Ring buffer with both ends |
| 1352 | [Product of Last K Numbers](https://leetcode.com/problems/product-of-the-last-k-numbers/)   | Stream queue               |
| 1696 | [Jump Game VI](https://leetcode.com/problems/jump-game-vi/)                                 | DP with monotonic deque    |

### Hard

| #   | Problem                                                                                                       | Pattern Variant                |
| --- | ------------------------------------------------------------------------------------------------------------- | ------------------------------ |
| 239 | [Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/)                               | Monotonic deque                |
| 295 | [Find Median from Stream](https://leetcode.com/problems/find-median-from-data-stream/)                        | Two-heap (priority queue)      |
| 862 | [Shortest Subarray with Sum at Least K](https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/) | Monotonic deque on prefix sums |
| 218 | [The Skyline Problem](https://leetcode.com/problems/the-skyline-problem/)                                     | Sweep line + heap              |
| 480 | [Sliding Window Median](https://leetcode.com/problems/sliding-window-median/)                                 | Two heaps with lazy delete     |

## Interview Tips

<AccordionGroup>
  <Accordion title="BFS vs DFS -- When to Choose Queue" icon="sitemap">
    Use a **queue (BFS)** when you need:

    * Shortest path in an unweighted graph
    * Level-by-level processing
    * Minimum number of steps/moves
    * "Nearest" or "closest" anything

    Use a **stack (DFS)** when you need:

    * All paths or all solutions
    * Backtracking
    * Detecting cycles (directed graphs)
    * Topological sort
  </Accordion>

  <Accordion title="Common Mistake: Using list.pop(0) in Python" icon="triangle-exclamation">
    Python's `list.pop(0)` is O(n) because it shifts every element left. For BFS with thousands of nodes, this turns your O(n) algorithm into O(n^2). Always use `collections.deque` with `popleft()` which is O(1).
  </Accordion>
</AccordionGroup>

## Practice Problems

<CardGroup cols={2}>
  <Card title="Sliding Window Max" icon="chart-line" href="https://leetcode.com/problems/sliding-window-maximum/">
    Monotonic deque technique
  </Card>

  <Card title="Implement Queue" icon="layer-group" href="https://leetcode.com/problems/implement-queue-using-stacks/">
    Two stacks approach
  </Card>

  <Card title="Number of Islands" icon="map" href="https://leetcode.com/problems/number-of-islands/">
    BFS exploration
  </Card>

  <Card title="Rotting Oranges" icon="lemon" href="https://leetcode.com/problems/rotting-oranges/">
    Multi-source BFS
  </Card>
</CardGroup>

## Interview Questions

### 1. Implement a queue using two stacks. What is the amortized time complexity of each operation?

**What interviewers are really testing:** Whether you understand the two-stack trick and, more importantly, whether you can analyze amortized complexity. Most candidates can implement it but stumble on proving why pop is O(1) amortized and not O(n).

**Strong Answer:**

* Use two stacks: an `inbox` for push and an `outbox` for pop/peek. Push always goes to `inbox` in O(1). For pop, if `outbox` is not empty, pop from it in O(1). If `outbox` is empty, transfer all elements from `inbox` to `outbox` (reversing the order to restore FIFO), then pop.
* The individual transfer step is O(n), but amortized analysis shows each element is moved at most once from `inbox` to `outbox` across its entire lifetime. So n operations cost O(n) total work for transfers, making each operation O(1) amortized.
* The key insight is lazy transfer: we only move elements when `outbox` is empty. This batches the expensive work. It is the same amortization argument as dynamic array resizing -- occasional expensive operations spread across many cheap ones.
* This is a real design pattern. Amazon SQS internally uses a similar two-buffer approach for message visibility. The pattern also appears in functional programming where queues are implemented using two lists.

**Red flag answer:** "Pop is O(n) because we might need to transfer everything." This misses amortized analysis, which is the entire point. Another red flag is transferring on every pop instead of only when `outbox` is empty.

**Follow-ups:**

1. What if we need to support a `peek` operation as well? Does it change the amortized complexity?
2. Can you implement a stack using two queues? What is the time complexity, and is it as efficient?

***

### 2. Explain how BFS uses a queue to traverse a graph level by level. Why can BFS not use a stack?

**What interviewers are really testing:** Deep understanding of why FIFO ordering is essential to BFS's correctness, not just the mechanics. They also want to see if you know what happens if you swap the queue for a stack.

**Strong Answer:**

* BFS explores nodes in order of their distance from the source. It enqueues the source, then repeatedly dequeues the front node, processes it, and enqueues all its unvisited neighbors. The FIFO property guarantees that all nodes at distance d are processed before any node at distance d+1.
* If you replace the queue with a stack, you get DFS (depth-first search), not BFS. A stack processes the most recently added neighbor first, diving deep into one branch before backing up. This destroys the level-by-level guarantee and means you can no longer use BFS to find shortest paths in unweighted graphs.
* The level-order trick: to know which nodes belong to which level, capture `queue.size()` at the start of each iteration and process exactly that many nodes. This is the pattern used in "Binary Tree Level Order Traversal," "Minimum Depth of Binary Tree," and "Word Ladder."
* Time complexity is O(V + E) for adjacency list representation. Space is O(V) in the worst case for the queue (when an entire level is in the queue at once -- imagine a complete binary tree's last level).

**Red flag answer:** "BFS just visits all nodes; it does not matter if you use a queue or stack." This is fundamentally wrong and shows a misunderstanding of graph traversal guarantees.

**Follow-ups:**

1. In "Rotting Oranges," why do we enqueue all initially rotten oranges at once before starting BFS? What is this pattern called?
2. How would you modify BFS to find the shortest path in a weighted graph? What changes about the data structure?

***

### 3. What is a monotonic deque, and how does it solve the "Sliding Window Maximum" problem in O(n)?

**What interviewers are really testing:** Whether you can maintain a running invariant on a double-ended queue and understand why the deque stores indices rather than values. This is one of the hardest queue-based patterns.

**Strong Answer:**

* A monotonic deque maintains elements in strictly decreasing order (for the maximum variant). The front of the deque always holds the index of the current window's maximum. When a new element arrives, we pop all elements from the back that are smaller than it -- they can never be the maximum of any future window because the new element is both larger and more recent.
* We store indices, not values, because we need to evict elements that have fallen outside the window. Before processing each new element, we check if the front index is outside the window bounds (`dq[0] <= i - k`) and pop it from the front.
* Each element is pushed and popped at most once across the entire traversal, so total operations are O(n). This avoids the O(n\*k) brute force of scanning each window.
* The deque invariant after processing index `i`: elements are in decreasing order of value, all indices are within the current window `[i-k+1, i]`, and the front is the maximum.

**Red flag answer:** "Use a max-heap for the window." A max-heap gives O(n log k) and does not efficiently remove expired elements. The candidate should know the deque gives O(n), which is strictly better. Another red flag is storing values instead of indices and not being able to handle window expiration.

**Follow-ups:**

1. How would you modify this to find the sliding window minimum instead?
2. What if the window size is not fixed but defined by a condition (like "sum of window at most target")? Can you still use a monotonic deque?

***

### 4. Design a moving average calculator for a data stream with a fixed window size. What data structure do you use and why?

**What interviewers are really testing:** Whether you can choose the right data structure for a stream processing problem and maintain a running aggregate efficiently. Simple problem, but it reveals clean thinking.

**Strong Answer:**

* Use a queue (deque) of fixed maximum size and maintain a running sum. When a new value arrives, add it to the queue and add it to the running sum. If the queue exceeds the window size, dequeue the oldest element and subtract it from the running sum. The average is `running_sum / queue_size`.
* Each `next()` call is O(1) time. Space is O(k) where k is the window size.
* The key optimization is the running sum. Without it, you would need to sum all k elements on every call, making each `next()` O(k). The running sum turns it into O(1) by only tracking the delta (add the new value, subtract the evicted value).
* Floating-point consideration: if the stream is very long and values are large, the running sum can accumulate floating-point error. In a production system, you might periodically recompute the sum from scratch or use Kahan summation for numerical stability.

**Red flag answer:** "Recompute the sum by iterating over the queue each time." That is O(k) per query instead of O(1). Another red flag is using a regular list and removing from the front in O(n) instead of using a deque with O(1) popleft.

**Follow-ups:**

1. What if instead of the mean, you needed the moving median? How does the data structure change?
2. How would you extend this to an exponentially weighted moving average (EWMA)? Do you still need a queue?

***

### 5. When would you choose a priority queue (heap) over a regular queue? Give specific problem examples.

**What interviewers are really testing:** Whether you understand that "queue" is not one-size-fits-all and can articulate when ordering by priority matters versus ordering by arrival time.

**Strong Answer:**

* A regular queue processes elements in FIFO order -- first in, first out. A priority queue processes elements by priority (highest or lowest value first), regardless of insertion order. Use a regular queue when order of arrival matters (BFS, task scheduling with fairness). Use a priority queue when urgency or weight matters (Dijkstra's shortest path, finding top-k elements, merge k sorted lists).
* Dijkstra's algorithm: BFS with a queue only works for unweighted graphs. For weighted graphs, we need to process the node with the smallest tentative distance next. A min-heap priority queue gives us this in O(log V) per extraction, leading to O((V + E) log V) total.
* Merge k sorted lists: we put the head of each list into a min-heap, extract the minimum, and push the next element from that list. This runs in O(n log k) where n is total elements and k is the number of lists.
* Top-k elements: maintain a min-heap of size k. For each element, if it is larger than the heap's minimum, replace the minimum. After processing all elements, the heap contains the k largest. This is O(n log k) time and O(k) space.

**Red flag answer:** "A priority queue is just a faster queue." No -- it serves a fundamentally different purpose: ordering by value rather than arrival. Another red flag is not being able to name a concrete problem that requires a priority queue.

**Follow-ups:**

1. What is the time complexity of building a heap from n elements? Why is it O(n) and not O(n log n)?
2. In Dijkstra's algorithm, what happens if you use a regular queue instead of a priority queue? Does the algorithm still produce correct results?

***

### 6. Explain how a circular queue (ring buffer) works. Where is it used in real systems?

**What interviewers are really testing:** Systems-level understanding and whether you know that the "queue" abstraction has different implementations with different trade-offs for different use cases.

**Strong Answer:**

* A circular queue uses a fixed-size array with two pointers: `head` (front) and `tail` (back). Both wrap around using modular arithmetic: `tail = (tail + 1) % capacity`. Enqueue places at `tail` and advances it; dequeue reads from `head` and advances it. When `head == tail`, the queue is either empty or full (distinguished by tracking count or leaving one slot empty).
* The advantage over a linked-list queue: no memory allocation on enqueue, no garbage collection pressure, cache-friendly contiguous memory. The disadvantage: fixed capacity -- you must decide the size upfront or handle resizing.
* Real-world uses: network packet buffers (Linux kernel's `sk_buff` ring), producer-consumer patterns in concurrent systems (Java's `ArrayBlockingQueue`, LMAX Disruptor), audio/video streaming buffers, and the CPU's reorder buffer in out-of-order execution.
* The LMAX Disruptor (used in high-frequency trading) achieves millions of messages per second using a ring buffer with careful lock-free design. It avoids cache-line bouncing by padding entries and uses sequence numbers instead of head/tail pointers.

**Red flag answer:** "I have never used a circular queue; linked-list queues are fine." This shows a lack of systems awareness. In performance-sensitive code, the choice between ring buffer and linked-list queue can be the difference between microsecond and millisecond latency.

**Follow-ups:**

1. How do you handle the case where the circular queue is full? What are the options, and which would you choose for a real-time system?
2. How does a lock-free ring buffer work in a multi-threaded producer-consumer scenario?

***

### 7. In the "Rotting Oranges" problem, all initially rotten oranges rot their neighbors simultaneously. How do you model this with BFS, and why is this different from standard BFS?

**What interviewers are really testing:** Understanding of multi-source BFS -- a critical variant where BFS starts from multiple sources at once. This pattern appears in many graph problems (0-1 BFS, shortest distance from any gate, etc.).

**Strong Answer:**

* This is multi-source BFS. Instead of starting from a single source, we enqueue all initially rotten oranges into the queue before starting the BFS loop. This is equivalent to adding a virtual super-source connected to all rotten oranges with zero-cost edges.
* The BFS then expands level by level. Each "level" corresponds to one minute of time. After processing all nodes at the current level (using the `level_size = len(queue)` trick), we increment the time counter. When the queue is empty, we have the minimum time.
* After BFS completes, check if any fresh oranges remain (cells with value 1 that were never reached). If so, return -1 -- not all oranges can be rotted.
* This same multi-source BFS pattern solves: "Walls and Gates" (distance from each empty room to nearest gate), "01 Matrix" (distance from each cell to nearest 0), and "Pacific Atlantic Water Flow" (start BFS from ocean borders).

**Red flag answer:** "Run BFS from each rotten orange separately and take the minimum." That is O(m*n \* number\_of\_rotten), not O(m*n). The multi-source approach processes every cell at most once, giving O(m\*n) total. The difference between single-source and multi-source BFS is exactly what the interviewer is probing.

**Follow-ups:**

1. What if some oranges rot faster than others (different weights)? Can you still use BFS, or do you need Dijkstra?
2. How would you modify this approach if oranges could also become "unrotten" after a certain time?

## Interview Q\&A Deep-Dive

The four questions below mirror the rich AccordionGroup format you will see in our microservices and other DSA chapters. Each one includes a strong answer framework, a real LeetCode example with full code, three senior follow-ups, common wrong answers, and further reading.

<AccordionGroup>
  <Accordion title="Q1: Design a moving average calculator from a data stream" icon="wave-square">
    **Strong Answer Framework:**

    1. **Clarify constraints first.** "Are values guaranteed to be integers? Is the window size fixed at construction or dynamic? What is the expected call volume -- millions per second or hundreds?"
    2. **State the data structure choice.** A `deque` (double-ended queue) of size at most `k`, plus a running sum scalar.
    3. **Walk through the invariant.** "After each call, the deque holds the last `k` values seen so far -- or all values if fewer than `k` have arrived. The running sum equals the sum of the deque."
    4. **Code the O(1) update.** Append the new value, add to running sum. If size exceeds `k`, popleft and subtract from running sum. Return `running_sum / size`.
    5. **Discuss numerical stability.** Floating-point error accumulates over very long streams. Mention Kahan summation or periodic full-recompute as production-grade options.

    **Real LeetCode Example -- LC 346: Moving Average from Data Stream**

    ```python theme={null}
    from collections import deque

    class MovingAverage:
        def __init__(self, size: int):
            self.size = size
            self.q = deque()
            self.total = 0.0

        def next(self, val: int) -> float:
            self.q.append(val)
            self.total += val
            if len(self.q) > self.size:
                self.total -= self.q.popleft()
            return self.total / len(self.q)
    ```

    Each call is O(1) time, O(k) space. The running-sum optimization is what turns a naive O(k)-per-call solution into O(1).

    <Note>
      **Senior Follow-up 1:** "What if instead of the mean, you needed the moving median?" -- The data structure changes fundamentally: you need two heaps (a max-heap for the lower half and a min-heap for the upper half) plus lazy deletion when the window slides. This is LC 480 (Sliding Window Median) and is materially harder than the average case.
    </Note>

    <Note>
      **Senior Follow-up 2:** "How would you extend this to an exponentially weighted moving average (EWMA)?" -- EWMA is `new_avg = alpha * val + (1 - alpha) * prev_avg`. You do not need a queue at all -- just one floating-point variable. EWMA forgets old values gradually rather than via a hard cutoff, which is what financial time series and metric pipelines (Datadog, Prometheus rate functions) actually use.
    </Note>

    <Note>
      **Senior Follow-up 3:** "Across millions of calls, your floating-point sum drifts. How do you handle that in production?" -- Use Kahan summation (a compensation variable that tracks lost low-order bits). Alternatively, recompute the sum from the deque every N calls -- amortizes to constant overhead and bounds error.
    </Note>

    **Common Wrong Answers:**

    * "Recompute the sum by iterating the queue every call." That is O(k) per call instead of O(1). Fails the implicit performance bar.
    * "Use a Python `list` and `pop(0)`." That is O(n) per pop and quietly turns the solution into O(n^2) over n calls.

    **Further Reading:**

    * [LC 346: Moving Average from Data Stream](https://leetcode.com/problems/moving-average-from-data-stream/)
    * [LC 480: Sliding Window Median](https://leetcode.com/problems/sliding-window-median/)
    * [LC 1352: Product of the Last K Numbers](https://leetcode.com/problems/product-of-the-last-k-numbers/)
  </Accordion>

  <Accordion title="Q2: Implement a queue using two stacks" icon="layer-group">
    **Strong Answer Framework:**

    1. **Name the structures.** `inbox` for incoming pushes, `outbox` for outgoing pops/peeks.
    2. **Push.** Always to `inbox` -- O(1).
    3. **Pop / peek.** If `outbox` is empty, *transfer everything* from `inbox` to `outbox` (which reverses order, restoring FIFO). Then pop from `outbox`.
    4. **Prove the amortized O(1).** Each element is pushed onto `inbox`, transferred once to `outbox`, and popped from `outbox` -- 4 operations total over its lifetime. Across n operations, total work is O(n), so each is O(1) amortized.
    5. **Critical detail.** Only transfer when `outbox` is empty. Transferring on every pop destroys the amortization and makes pop O(n) worst-case AND average-case.

    **Real LeetCode Example -- LC 232: Implement Queue using Stacks**

    ```python theme={null}
    class MyQueue:
        def __init__(self):
            self.inbox = []   # for push
            self.outbox = []  # for pop/peek

        def push(self, x: int) -> None:
            self.inbox.append(x)

        def pop(self) -> int:
            self._shift()
            return self.outbox.pop()

        def peek(self) -> int:
            self._shift()
            return self.outbox[-1]

        def empty(self) -> bool:
            return not self.inbox and not self.outbox

        def _shift(self):
            if not self.outbox:           # ONLY transfer when outbox is empty
                while self.inbox:
                    self.outbox.append(self.inbox.pop())
    ```

    <Note>
      **Senior Follow-up 1:** "Can you implement a stack using two queues? What is the time complexity, and is it as efficient?" -- Yes, but the asymmetry is interesting: making `push` O(n) (rotate the queue so the new element is at the front) lets you keep `pop` and `top` at O(1). Alternatively, make `pop` O(n). Unlike the queue-via-stacks case, there is no clever amortization -- one operation is always O(n).
    </Note>

    <Note>
      **Senior Follow-up 2:** "What if multiple threads call push and pop simultaneously?" -- The two-stack invariant breaks under concurrency: a `pop` thread can observe `outbox` empty and start transferring while a `push` thread mutates `inbox`. You need a single lock around the whole class, or switch to `LinkedBlockingQueue` (Java) / `queue.Queue` (Python) for thread safety. Two stacks plus a lock is rarely worth it -- just use a real concurrent queue.
    </Note>

    <Note>
      **Senior Follow-up 3:** "What is the worst-case latency of a single pop? Why might that matter in production?" -- Worst case is O(n): if the inbox has accumulated many pushes since the last pop, the next pop triggers a full transfer. For real-time systems with strict latency tails (trading, gaming), amortized O(1) is not good enough -- you need worst-case O(1), which requires a different structure (linked list or ring buffer).
    </Note>

    **Common Wrong Answers:**

    * "Pop is O(n)." Misses the amortized argument -- this is the entire point of the question.
    * "Transfer on every pop." Doubles the work and breaks the amortization.
    * "Use Java's `Stack` class." `Stack` extends `Vector` and is synchronized; use `ArrayDeque` instead.

    **Further Reading:**

    * [LC 232: Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/)
    * [LC 225: Implement Stack using Queues](https://leetcode.com/problems/implement-stack-using-queues/)
    * [LC 622: Design Circular Queue](https://leetcode.com/problems/design-circular-queue/)
  </Accordion>

  <Accordion title="Q3: Sliding window maximum -- why monotonic deque beats a heap" icon="chart-line">
    **Strong Answer Framework:**

    1. **State the brute force.** For each of `n - k + 1` windows, scan k elements -- O(n \* k). Times out on large inputs.
    2. **Compare two optimized approaches.** Max-heap gives O(n log k). Monotonic deque gives O(n) -- strictly better.
    3. **Explain the deque invariant.** Indices in the deque correspond to values in strictly decreasing order. The front is always the index of the current window's maximum.
    4. **Walk through the three steps per element.** (a) Evict expired indices from the front. (b) Evict useless tail indices whose values are smaller than the new element. (c) Append the new index. Read max from front once the window has formed.
    5. **Justify "indices, not values".** Without indices you cannot tell whether the front has fallen out of the window.

    **Real LeetCode Example -- LC 239: Sliding Window Maximum**

    ```python theme={null}
    from collections import deque

    def maxSlidingWindow(nums, k):
        dq = deque()              # holds INDICES; values at those indices strictly decrease
        result = []
        for i, x in enumerate(nums):
            # 1. evict expired
            while dq and dq[0] <= i - k:
                dq.popleft()
            # 2. evict useless tail
            while dq and nums[dq[-1]] < x:
                dq.pop()
            # 3. append
            dq.append(i)
            if i >= k - 1:
                result.append(nums[dq[0]])
        return result
    ```

    <Note>
      **Senior Follow-up 1:** "How would you modify this for the sliding window minimum instead?" -- Flip the comparison: maintain a strictly increasing deque, evict tail indices whose values are larger than the new element. Front is now the window minimum. Same O(n).
    </Note>

    <Note>
      **Senior Follow-up 2:** "Why does a max-heap not achieve O(n)?" -- A heap can extract the max in O(log k), but it cannot remove an arbitrary element when it expires from the window. You either accept O(n) lazy deletion (peek the max, discard if out of window, repeat) or use a removable heap with a hashmap of (value, count) which is more complex. The monotonic deque sidesteps this entirely.
    </Note>

    <Note>
      **Senior Follow-up 3:** "What if the window size is dynamic -- determined by a condition like prefix-sum at most target?" -- The deque approach generalizes via LC 862 (Shortest Subarray with Sum at Least K), where you use a monotonic deque on prefix sums. The eviction rule becomes "front is too small to be useful" rather than "front is out of window." Same O(n) amortized.
    </Note>

    **Common Wrong Answers:**

    * "Use a max-heap." Gets O(n log k); strictly worse than the deque's O(n).
    * "Store values in the deque, not indices." Cannot detect window expiration -- the algorithm produces wrong results when the max value sits before the window starts.
    * "Use a `SortedList`." O(n log k) and library-dependent.

    **Further Reading:**

    * [LC 239: Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/)
    * [LC 1438: Longest Subarray with Absolute Diff at most Limit](https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/)
    * [LC 862: Shortest Subarray with Sum at Least K](https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/)
  </Accordion>

  <Accordion title="Q4: BFS multi-source pattern (Rotting Oranges)" icon="lemon">
    **Strong Answer Framework:**

    1. **Recognize the multi-source signature.** Multiple starting points expand simultaneously. Single-source BFS would over-process.
    2. **Pre-load the queue.** Before the BFS loop starts, scan the grid and enqueue every initial source (every rotten orange) along with their starting time of 0.
    3. **Process by levels.** Use the `level_size = len(queue)` snapshot trick to advance "minutes" one level at a time.
    4. **Bookkeep fresh count.** Track how many fresh oranges remain. Each successful infection decrements it. If non-zero at the end, return -1.
    5. **Why not run single-source BFS from each rotten orange?** That is O(grid \* num\_rotten) -- with 10x10 grid and 50 rotten oranges, that is 500x slower than multi-source.

    **Real LeetCode Example -- LC 994: Rotting Oranges**

    ```python theme={null}
    from collections import deque

    def orangesRotting(grid):
        rows, cols = len(grid), len(grid[0])
        q = deque()
        fresh = 0
        # 1. seed the queue with ALL rotten oranges at time 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:
                    q.append((r, c, 0))
                elif grid[r][c] == 1:
                    fresh += 1

        if fresh == 0:
            return 0                              # nothing to rot

        minutes = 0
        directions = [(-1,0),(1,0),(0,-1),(0,1)]
        while q:
            r, c, t = q.popleft()
            minutes = t
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    q.append((nr, nc, t + 1))

        return minutes if fresh == 0 else -1
    ```

    <Note>
      **Senior Follow-up 1:** "What if some oranges rot faster than others (different weights)?" -- You can no longer use plain BFS because the path with the fewest hops is no longer the shortest path. You must upgrade to Dijkstra with a min-heap priority queue. The structural change is the data structure, not the algorithm shape.
    </Note>

    <Note>
      **Senior Follow-up 2:** "What other problems share this multi-source BFS pattern?" -- LC 542 (01 Matrix -- start BFS from every 0, find distance to nearest 0 for each cell), LC 286 (Walls and Gates -- start from every gate), LC 417 (Pacific Atlantic Water Flow -- start from every ocean border). The pattern's signature is "compute distance from any source" rather than "compute distance from a specific source."
    </Note>

    <Note>
      **Senior Follow-up 3:** "What if oranges can become unrotten after a delay?" -- Now you have a temporal dependency: BFS no longer suffices because state can revert. You need a simulation with a discrete-time loop, or model it as a state-space search (BFS over (grid\_state, time) pairs) -- which is exponential and infeasible for non-trivial grids. The conversation often pivots to "is there a smarter formulation," like detecting periodicity.
    </Note>

    **Common Wrong Answers:**

    * "Run BFS from each rotten orange separately and take the min over each cell." Correct answer, wrong complexity -- O(grid \* num\_rotten) instead of O(grid).
    * "Use DFS instead of BFS." DFS does not guarantee shortest path / minimum time -- it can revisit cells with longer paths first.
    * "Forget to check for unreachable fresh oranges." Returns wrong answer when the grid has isolated fresh oranges.

    **Further Reading:**

    * [LC 994: Rotting Oranges](https://leetcode.com/problems/rotting-oranges/)
    * [LC 542: 01 Matrix](https://leetcode.com/problems/01-matrix/)
    * [LC 286: Walls and Gates](https://leetcode.com/problems/walls-and-gates/)
  </Accordion>
</AccordionGroup>