Common Queue Patterns
Recognizing the appropriate queue pattern is crucial in coding interviews. The two primary patterns are breadth-first search (BFS) and monotonic queues. BFS is used for layer-by-layer exploration in graphs and trees, ensuring nodes are processed in the order they are discovered, making it ideal for shortest-path problems. In contrast, monotonic queues maintain a specific order while sliding across an array, allowing efficient access to maximum or minimum values within a window. Understanding the signals for each pattern helps in selecting the right approach for various interview problems.
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
...