Common Queue Patterns
Explore the two essential queue patterns used in coding interviews: breadth-first search for level-by-level graph or tree traversal, and monotonic queue for efficient sliding window maximum or minimum queries. Understand when and how to apply each pattern to solve common algorithmic challenges in JavaScript.
We'll cover the following...
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. In JavaScript, this is usually implemented with an array and a head pointer rather than repeatedly shifting from the front.
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
...