Queue [mp]

Micro pattern¶

Description¶

Process states in first-in, first-out order to preserve discovery or level order.

Problems¶

Level-order traversal¶

Process the current queue contents before their newly discovered successors.

• 102. Binary Tree Level Order Traversal (Top Easy)
• 103. Binary Tree Zigzag Level Order Traversal (Top Medium)
• 329. Longest Increasing Path in a Matrix (Top Hard)
• 863. All Nodes Distance K in Binary Tree (Graph Theory)
• 934. Shortest Bridge (Graph Theory)

Multi-source traversal¶

Seed a queue with all initially available states.

• 542. 01 Matrix (Google Prep)
• 207. Course Schedule (Top Hard)
• 210. Course Schedule II (Top Hard)
• 329. Longest Increasing Path in a Matrix (Top Hard)
• 802. Find Eventual Safe States (Graph Theory)
• 934. Shortest Bridge (Graph Theory)
• 1203. Sort Items by Groups Respecting Dependencies (Graph Theory)
• 1857. Largest Color Value in a Directed Graph (Graph Theory)

Frontier-based traversal¶

Generate successive BFS frontiers in discovery order.

• BFS (DSA)
• 127. Word Ladder (Top Hard)
• 1129. Shortest Path with Alternating Colors (Graph Theory)
• 1926. Nearest Exit from Entrance in Maze (Graph Theory)
• 433. Minimum Genetic Mutation (Graph Theory)
• 1091. Shortest Path in Binary Matrix (Graph Theory)
• 864. Shortest Path to Get All Keys (Graph Theory)

Monotonic deque¶

Expire old indices at the front and remove dominated candidates at the back.

• 239. Sliding Window Maximum (Top Hard)