Queue Patterns – Optimized for Interview Prep

Queues are fundamental for solving problems that involve order of processing, level-wise traversal, streaming data, and maintaining dynamic maximum/minimum values.

The key property of a queue is FIFO (First In, First Out). Many advanced problems extend this concept using:

• Deque (Double-ended queue) → Efficient sliding window operations
• Priority Queue (Heap) → Efficient min/max retrieval
• Multiple Heaps → Streaming median problems

Once you understand the input structure + keywords + processing order, selecting the correct queue pattern becomes automatic.

---

Pattern Table (Simplified & Prioritized, 4 Columns)

Pattern	Typical Question Types	Keywords / Detection Cues	Why Use / Notes
BFS / Level Order	Shortest path, Level traversal	breadth, level, neighbor	Queue processes nodes level by level; guarantees shortest path in unweighted graphs.
Sliding Window / Max	Max/min in subarray/window	window, max/min, size k	Deque maintains useful candidates; O(n) efficient window processing.
Priority Queue / Heap	Top k elements, Dijkstra	priority, min/max, kth, smallest	Heap gives O(log n) insert/delete and O(1) min/max access.
Two Heap (Bonus)	Median of running stream	median, stream, lower/upper half	Maintain max-heap + min-heap to balance halves dynamically.

---

Queue Patterns – Detection & Usage Guide

---

1. BFS / Level Order – Common (Queue, Tree, Graph)

When to use / Detection cues:

• Input structure: Tree, graph, or grid.
• Question keywords: breadth, level, neighbor, minimum steps.
• Problem hints: Traverse nodes level by level; find shortest path in unweighted graph.
• Why it works: Queue ensures nodes are processed in order of distance from source.

Typical questions:

• Shortest path in unweighted graph
• Level order traversal of binary tree
• Minimum moves in grid/maze

Mental trigger:

“Level-by-level” + “minimum steps” → BFS using Queue

---

2. Sliding Window / Max (Using Deque) – Common (Queue, Arrays)

When to use / Detection cues:

• Input structure: Array or string.
• Question keywords: window of size k, max/min, subarray.
• Problem hints: Need max/min for every contiguous subarray of size k.
• Why it works: Deque stores useful candidates only; removes smaller elements from back to maintain order.

Typical questions:

• Maximum in every subarray of size k
• Minimum in sliding window
• First negative number in every window

Mental trigger:

“Window size k” + “max/min” → Deque-based Sliding Window

---

3. Priority Queue / Heap – Common (Heap, Graph, Arrays)

When to use / Detection cues:

• Input structure: Array, graph, or streaming input.
• Question keywords: top k, smallest/largest, priority.
• Problem hints: Need efficient retrieval of min/max repeatedly.
• Why it works: Heap maintains sorted structure partially; root always gives smallest/largest.

Typical questions:

• Kth largest/smallest element
• Top k frequent elements
• Dijkstra’s shortest path

Mental trigger:

“Top k” + “efficient min/max” → Priority Queue

---

4. Two Heap Pattern – Rare / Bonus (Streaming Problems)

When to use / Detection cues:

• Input structure: Stream of numbers.

• Question keywords: median, running, continuous.

• Problem hints: Need median after each insertion.

• Why it works:

  • Max-heap → stores lower half
  • Min-heap → stores upper half
  • Balance sizes to compute median efficiently

Typical questions:

• Median of running stream
• Dynamic percentile calculation

Mental trigger:

“Running median” → Two Heaps

---

Mini Notes / Tips

### Tips

- Always identify if the problem requires FIFO processing → use Queue.
- For shortest path in unweighted graph → BFS.
- For max/min in window of size k → Deque.
- For repeated min/max extraction → Priority Queue.
- For streaming median → Two Heaps.
- Many queue problems overlap with graph or array patterns.
- Mental map: Input structure → Keyword → Required order → Choose Queue variation.