Common Queue Patterns
Explore common queue patterns used in coding interviews, focusing on breadth-first search for graph and tree traversal, and monotonic queues for efficient sliding window problems. Understand when to apply each pattern, their complexity, and solve typical interview challenges with confidence.
Recognizing a queue as the right data structure is only the first step. The next step is knowing which pattern to apply. This lesson covers the two most important queue patterns in coding interviews: breadth-first search and the monotonic queue. They represent two fundamentally different uses of a queue, and together they cover the majority of queue-based interview problems.
Interview lens: The signal for both patterns is usually recognizable within the first minute of reading a problem. A problem about layer-by-layer exploration or shortest path is almost always BFS. A problem about the maximum or minimum within a sliding window is almost always a monotonic queue. Building that reflex is what this lesson is about.
Breadth-first search
The BFS pattern uses a queue to explore nodes layer by layer. We enqueue the starting node, then repeatedly dequeue a node, process it, and enqueue its unvisited neighbors. Because we enqueue and dequeue from opposite ends, we always process nodes in the order we discovered them, which guarantees that we visit every node at the current depth before moving to the next.
Trap (not marking nodes as visited before enqueuing): Nodes must be marked as visited at the moment they are enqueued, not when they are dequeued. Marking on the dequeue allows the same node to be enqueued multiple times before it is processed, which leads to incorrect results and, in graph problems, can cause infinite loops.
This ordering property is what makes BFS the right pattern for shortest-path problems in unweighted graphs and level-order traversal in trees. A stack-based DFS explores as deeply as possible before backtracking. BFS spreads outward uniformly, which is exactly what these problems need.
Time and space complexity
Time
...