0-1 BFS (deque)
Edge weights 0 or 1: push cost-0 moves to the front, cost-1 to the back.
The deque is sorted by distance, with at most two distinct values.
01The intuition
Start with what you would do by hand
Imagine a 3×3 grid of rooms. Each room has an arrow painted on the floor pointing to one neighbour. Walking in the direction of the arrow is free. Walking any other direction means you must repaint the arrow first, and every repaint costs 1 rupee. You start at the top-left room and want to reach the bottom-right room spending as little as possible.
By hand you would try routes: follow arrows as long as they lead somewhere useful, and repaint only when stuck. On a 3×3 grid you can try every route; there are only a handful. On a 100×100 grid there are more routes than you could list in a lifetime, so trying routes is out. We need a method that visits each room once and still finds the cheapest cost.
Build the structure, one piece at a time
Begin with an ordinary queue: a line of rooms waiting to be looked at. You add rooms at the back and take them from the front. Plain breadth-first search uses exactly this, and it finds the fewest steps, because rooms are taken out in the order they were put in.
Now the twist: steps are not all equal. An arrow step costs 0, a repaint step costs 1. If we used a plain queue, a cheap 0-cost room might sit behind an expensive 1-cost room and be processed too late.
So we upgrade the queue into a deque, a double-ended queue: you may add to the front as well as the back. The one new rule of the pattern is:
- a move that costs 0 goes to the front of the deque;
- a move that costs 1 goes to the back.
Watch the deque on the video's grid, where the top row's arrows all point right. Start: deque = [(0,0) cost 0]. Take (0,0). Its arrow points to (0,1), cost 0, so (0,1) goes to the front; the move down to (1,0) costs 1 and goes to the back: deque = [(0,1) 0, (1,0) 1]. Take (0,1): its arrow gives (0,2) at cost 0, pushed to the front; (1,1) at cost 1 to the back: deque = [(0,2) 0, (1,0) 1, (1,1) 1]. The 0-cost rooms always jump the line, so every room is reached by its cheapest route first.
Why it is correct
The invariant: the costs in the deque, read from front to back, never go down, and only two values ever appear at once, some d and some d+1. Why does each push keep this true? When we take a room of cost d from the front, a 0-cost neighbour also has cost d, so putting it at the front keeps the front equal to d. A 1-cost neighbour has cost d+1, the largest value present, so the back is the right place. Nothing is ever pushed with cost below the front or above the back.
Because the deque is always sorted by cost, the room taken from the front is always the cheapest unsettled room. That is exactly what Dijkstra's algorithm needs, so the first time a room is taken out, its cost is final.
Why it is fast
Every room is settled once, and when it is settled we look at each of its edges once. For V rooms and E edges that is
work = V + E
Dijkstra with a heap would spend log V per push, giving E log V. Here a push is a constant-time deque operation, because the sortedness comes for free from the 0/1 rule. On a 100×100 grid that is about 40,000 operations instead of about 500,000.
How to recognise it in an interview
Listen for a grid or graph where some moves are free and others cost exactly 1, or where the cost is "number of changes": flipping a direction, removing an obstacle, reversing an edge. The first thing to say: "every edge costs 0 or 1, so I can replace the heap with a deque and get linear time." Minimum Cost to Make at Least One Valid Path in a Grid is the textbook case: following the painted arrow costs 0, overriding it costs 1. Minimum Obstacle Removal to Reach Corner is the same with cells: stepping on an empty cell is 0, stepping on an obstacle is 1.
02The idea in one line
Edge weights 0 or 1: push cost-0 moves to the front, cost-1 to the back.
Reach for it when: Minimum cost to make a valid path, obstacle removal, minimum flips.
Cost: O(V + E) time.
03The walk-through, step by step
The video works one example: Minimum Cost Valid Path on a 3×3 grid. These are its captions in order, so you can follow without the video or check a step you missed.
- Start at (0,0) with cost 0
- Settle (0,0) at cost 0: arrow move → front, others → back (+1)
- Settle (0,1) at cost 0: arrow move → front, others → back (+1)
- Settle (0,2) at cost 0: arrow move → front, others → back (+1)
- Settle (1,2) at cost 0: arrow move → front, others → back (+1)
- Settle (1,1) at cost 0: arrow move → front, others → back (+1)
- Settle (1,0) at cost 0: arrow move → front, others → back (+1)
- Settle (2,0) at cost 0: nothing improves
- Settle (2,2) at cost 1: nothing improves
- Settle (2,1) at cost 1: nothing improves
- Bottom-right reached with cost 1: one arrow changed
- A deque instead of a heap: O(V + E) for 0/1 weights
04Asked at Google
4 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| Shortest Path in a Grid with Obstacles Elimination | Hard | 34 | last 6 months |
| Minimum Cost to Make at Least One Valid Path in a Grid | Hard | 29 | |
| Minimum Obstacle Removal to Reach Corner | Hard | 22 | |
| Minimum Cost Path with Edge Reversals | Medium | 21 |
05Related patterns
Other patterns in Graphs: Grid flood fill (components), Multi-source BFS, BFS shortest path (unweighted), BFS over an augmented state, DFS three-colour cycle detection, Topological sort (Kahn's), Union–Find (disjoint sets), Dijkstra (weighted shortest path), Bellman–Ford with k rounds, Minimum spanning tree, Bipartite colouring, Eulerian path (Hierholzer), Bridges / articulation (low-link), Clone / traverse with a visited map, Implicit graph (states as nodes).