0-1 BFS and Deque Shortest Paths

Plain BFS finds shortest paths because every edge costs the same, so the queue is sorted by distance without anyone sorting it. Dijkstra handles arbitrary weights by paying for a heap. 0-1 BFS is the case in between: when every weight is 0 or 1, at most two distinct distances are ever in flight, and a deque keeps them ordered for free. Push a 0-edge to the front, a 1-edge to the back, and you have Dijkstra’s answer in Dijkstra-minus-the-log time.

The reason it earns a page of its own is not the speed. It is that a large family of grid problems — “minimum obstacles to remove”, “minimum cells to rotate”, “minimum lane switches” — are 0-1 graphs in disguise, and the reframing is the entire difficulty. Once you see that moving with the arrow is free and moving against it costs 1, LeetCode 1368 stops being a hard problem and becomes eleven lines.

What you’ll learn

Why a deque is a sufficient priority queue when weights are $\{0, 1\}$ , and the two-layer invariant that makes it correct.
The exact template, including the guard that makes duplicate pushes harmless.
How to spot a 0-1 graph inside a grid problem where no weights are mentioned.
Where the technique stops: weight 2, negative weights, and why “0 and k” needs a small change.

The cue

You need a shortest path or minimum cost, and every move costs either nothing or one unit. The words are usually free, already, no cost, or without changing, set against one operation, one removal, one rotation.
A grid problem asks for the minimum number of somethings to change in order to make a path exist: obstacles removed, arrows redirected, lanes switched, walls broken.
You wrote Dijkstra, it passed, and the follow-up is “can you drop the log factor”.

The reframe: the state is the cell (or node), and the weight is the price of the move you make to get there — not a property of the cell itself. In LC 1368 the grid stores an arrow per cell; following it is weight 0, going any other direction is weight 1. Nothing in the statement mentions a graph, and the whole problem is building that one.

Reach for something else when a weight of 2 or more can appear (Dijkstra), when weights can be negative (Bellman-Ford), or when every weight is 1 (plain BFS — do not carry the deque machinery you do not need).

Visual intuition

Watch the deque panel, not the graph. It never holds more than two distinct distances at once — that is the invariant, and it is the reason no heap is needed.

graph0-1 BFS: a 0-edge jumps the queue, a 1-edge joins the backO(V + E) — no heap

deque

A:0

1from collections import deque2 3def bfs01(graph, start):4    dist = {v: inf for v in graph}5    dist[start] = 06    dq = deque([start])7    while dq:8        v = dq.popleft()9        for u, wt in graph[v]:        # wt is 0 or 1 only10            if dist[v] + wt < dist[u]:11                dist[u] = dist[v] + wt12                if wt == 0:13                    dq.appendleft(u)  # same layer — jump the queue14                else:15                    dq.append(u)      # next layer — back of the queue16    return dist

deque1

seedEvery weight in this graph is 0 or 1, which is the entire precondition. Dijkstra would work, but its heap is doing no useful sorting: with only two possible weights, at most two distinct distances are ever in flight, so a **deque** keeps them in order for free. Start at A with distance 0.

1/8

Compare with the Dijkstra trace on the shortest-paths page: same answers, same relaxation condition, no ordering structure. The deque stays sorted because a 0-edge produces a node in the current layer and a 1-edge one in the next, and those are the only two possibilities.

Side by side with the two algorithms it sits between:

	frontier structure	ordering comes from	cost
BFS (all weights 1)	queue	one layer at a time	$O(V + E)$
0-1 BFS (weights 0/1)	deque	0 to the front, 1 to the back	$O(V + E)$
Dijkstra (any weight ≥ 0)	heap	explicit comparisons	$O((V + E)\log V)$

The template

bfs01.py

from collections import deque
from math import inf
 
 
def bfs01(adj, start, n):
    """Shortest distances from `start` when every weight in `adj` is 0 or 1."""
    dist = [inf] * n
    dist[start] = 0
    dq = deque([start])
 
    while dq:
        v = dq.popleft()
        for u, wt in adj[v]:                 # wt in (0, 1)
            if dist[v] + wt < dist[u]:       # the guard that makes repeats safe
                dist[u] = dist[v] + wt
                if wt == 0:
                    dq.appendleft(u)         # same layer — jump the queue
                else:
                    dq.append(u)             # next layer — back of the queue
    return dist
 
 
# LC 1368 -- minimum cost to make at least one valid path in a grid.
# The grid's arrows define the free moves; every other move costs 1.
def min_cost(grid):
    rows, cols = len(grid), len(grid[0])
    arrow = {1: (0, 1), 2: (0, -1), 3: (1, 0), 4: (-1, 0)}   # right left down up
    dist = [[inf] * cols for _ in range(rows)]
    dist[0][0] = 0
    dq = deque([(0, 0)])
 
    while dq:
        r, c = dq.popleft()
        for code, (dr, dc) in arrow.items():
            nr, nc = r + dr, c + dc
            if not (0 <= nr < rows and 0 <= nc < cols):
                continue
            wt = 0 if grid[r][c] == code else 1     # following the arrow is free
            if dist[r][c] + wt < dist[nr][nc]:
                dist[nr][nc] = dist[r][c] + wt
                if wt == 0:
                    dq.appendleft((nr, nc))
                else:
                    dq.append((nr, nc))
    return dist[rows - 1][cols - 1]
 
 
print(min_cost([[1, 1, 1, 1], [2, 2, 2, 2], [1, 1, 1, 1], [2, 2, 2, 2]]))  # expect 3
print(min_cost([[1, 1, 3], [3, 2, 2], [1, 1, 4]]))                          # expect 0
print(min_cost([[1, 2], [4, 3]]))                                           # expect 1

Three details in that template are load-bearing:

if dist[v] + wt < dist[u] is checked on push, not on pop. A node can be pushed several times; the guard means a stale copy popped later improves nothing and falls through. This replaces Dijkstra’s if d > dist[v]: continue.
No visited set. A node’s distance can improve after it has been popped (via a 0-edge discovered later), so marking it visited is wrong — this is the difference from plain BFS, and the single most common way to break 0-1 BFS.
appendleft vs append is the only branch. Everything else is BFS.

Dry run

The graph in the visualization: undirected, weights on the edges, start A.

text

A --0-- B        A--0--B, A--1--C, B--1--D
|       |        C--0--D, C--1--E, D--0--E
1       1
|       |
C --0-- D --0-- E
 \--1---------/

step	pop	improvements	deque afterwards	distinct distances in it
0	—	seed	`[A:0]`	0
1	`A` (d=0)	`B→0` front (weight 0), `C→1` back	`[B:0, C:1]`	0 and 1
2	`B` (d=0)	`D→1` back	`[C:1, D:1]`	1
3	`C` (d=1)	`E→2` back	`[D:1, E:2]`	1 and 2
4	`D` (d=1)	`E→1` front — improved from 2	`[E:1, E:1]`	1
5	`E` (d=1)	none: `C` needs 2, `D` already 1	`[E:1]`	1
6	`E` again	none — stale duplicate, guard rejects everything	`[]`	—

Final: A=0, B=0, C=1, D=1, E=1.

What the trace shows that the code hides:

The deque is never out of order, and nobody sorted it. At step 1 it holds B:0 in front of C:1 because a 0-edge was pushed to the front and a 1-edge to the back. That is the induction step of the correctness proof: if the deque holds only distances $d$ then $d+1$ , pushing $d$ at the front and $d+1$ at the back preserves exactly that shape — never three distinct values, so never a wrong pop order.
E is improved at step 4, after it was already in the deque. It entered at distance 2 via C, and the 0-edge D→E lowered it to 1. This is precisely why a visited set is wrong here and correct for plain BFS: in a 0-1 graph a node’s distance can still fall after it has been discovered, and even after it has been popped.
Step 6 pops E a second time and it costs nothing. The improvement at step 4 pushed a second copy rather than deleting the old one — the deque has no decrease-key. The strict < guard makes the duplicate a no-op, which is the whole reason we can skip Dijkstra’s stale-entry check.
A and B share distance 0. A 0-edge means two nodes are in the same layer, so “layer” no longer means “one round of the queue”.

Complexity

	Time	Space
0-1 BFS	$O(V + E)$	$O(V)$ for `dist`, $O(V)$ for the deque
Dijkstra on the same graph	$O((V + E)\log V)$	$O(V + E)$ heap entries
On an $R \times C$ grid with 4 moves	$O(RC)$	$O(RC)$

Each edge is relaxed a constant number of times: a node’s distance only ever decreases, it can take at most two values in the deque’s window, and each improvement pushes once. The deque holds at most $O(V)$ entries — some of them stale, which is why the pop-side guard matters.

The variant map

Problem	The 0-1 graph hiding inside it	Weight 0	Weight 1
LC 1368 Min cost to make a valid path	cell → neighbouring cell	the move the cell’s arrow points to	any other of the 4 moves
LC 2290 Min obstacle removal	cell → neighbouring cell	stepping onto an empty cell	stepping onto an obstacle
LC 1824 Minimum sideway jumps	(lane, position) → next state	advancing a position in the same lane	switching lane at the same position
Break at most k walls	(cell, walls used)	empty neighbour	wall — plus a state dimension for the budget
Min flips to make a path	cell → neighbouring cell	matching bit	flipped bit
Grid with 8 moves	same	free direction	any other
LC 1091 Shortest path in binary matrix	all moves cost 1	—	plain BFS; the deque buys nothing
LC 1631 Path with minimum effort	weights are heights	—	not 0-1: Dijkstra, or binary search + BFS

The pattern generalises in one more direction worth knowing: a multi-source 0-1 BFS is the same algorithm seeded with several nodes at distance 0 pushed at the front, exactly as multi-source BFS seeds a plain queue.

Pitfalls

Using a visited set. In 0-1 BFS a node’s distance can improve after it has been popped, because a 0-edge may reach it from a node processed later. Marking visited yields answers that are too large — plausible, not obviously broken.
<= instead of < in the guard. With 0-weight edges this pushes forever and hangs. The strict comparison is what terminates the loop.
append for the 0-edge and appendleft for the 1-edge. Reversed pushes still terminate and still return a path length, just not the shortest. Test on an input where the free route is longer in hops than the paid one, or the bug hides.
Costing the cell instead of the move. In LC 2290 the obstacle you pay for is the cell you step onto, so the weight belongs to the destination. Charging the source double-counts the first cell and misses the last.
Forgetting the start cell’s own cost. If the source itself is an obstacle in a problem that charges for entering obstacles, dist[start] is 1, not 0. Read the statement.
Reaching for it when all weights are 1. Plain BFS with a queue is the same asymptotics and less to get wrong. Using a deque is not a bonus.
Assuming Dijkstra would time out. It usually does not — $\log(RC)$ on a $10^5$ -cell grid is ~17. Present 0-1 BFS as the better fit for the weights, not as a rescue from TLE you have not measured.

Interview follow-ups

They ask	What they’re checking	The answer
“Why is a deque enough here?”	The invariant	Because only two distinct distances are ever live: from a node at distance $d$ , a 0-edge produces $d$ and a 1-edge produces $d+1$ . Pushing $d$ at the front and $d+1$ at the back keeps the deque sorted by construction, so no comparisons are needed
“What breaks if a weight of 2 appears?”	Boundaries	The two-layer invariant fails — a node at $d+2$ would have to be inserted in the middle. Use Dijkstra, or a bucket queue with $k+1$ buckets if the weights are small integers
“Do you need a visited set?”	The key difference from BFS	No, and adding one is a bug: a 0-edge can improve a node after it has been popped. The `dist[v] + wt < dist[u]` guard does the job, and it also makes duplicate deque entries harmless
“Prove the deque stays sorted”	Rigour	Induction on pops. The deque holds only $d$ then $d+1$ ; popping $d$ pushes $d$ at the front (still the minimum) or $d+1$ at the back (still the maximum). The window never widens
“Where is the graph in LC 1368?”	Modelling	Nodes are cells, edges are the four moves, and the weight is a property of the move: following the cell’s arrow is free, any other direction costs one redirection. The grid’s numbers are edge weights, not node values
“Now allow breaking at most `k` walls”	State-space thinking	Add the budget to the state: `(cell, walls_used)`, still 0-1 weighted, so the same deque works over $V \times (k+1)$ states. This is the extra-state BFS idea composed with this one
“Same question, but return the path”	Bookkeeping	Store a parent per node, overwritten whenever `dist` improves, and walk back from the target. Parents recorded on push-without-improvement give a wrong path
“Multi-source version?”	Generalisation	Seed every source at distance 0 at the front of the deque. Identical to multi-source BFS, and the invariant is unchanged

Practice

5 problems

0 easy3 medium2 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

1091Shortest Path in Binary Matrixmedium
1631Path With Minimum Effortmedium
1824Minimum Sideway Jumpsmedium
1368Minimum Cost to Make at Least One Valid Path in a Gridhard
2290Minimum Obstacle Removal to Reach Cornerhard

Exercises

LC 1368 — Minimum Cost to Make at Least One Valid Path in a Grid · Hard

LC 2290 — Minimum Obstacle Removal to Reach Corner · Hard

LC 1824 — Minimum Sideway Jumps · Medium

Self-check

pch.quizTag 0-1 BFS — self-check

Why is a deque a sufficient priority queue when every weight is 0 or 1?

pch.quizShowAnswer

B — Because only two distinct distances are ever live: from a node at distance d, a 0-edge yields d and a 1-edge yields d+1 — so pushing to the front and back keeps it sorted with no comparisons — The two-layer window is the whole argument, and it is also what fails the moment a weight of 2 appears — that node would have to be inserted in the middle of the deque.
Should 0-1 BFS use a `visited` set, as plain BFS does?

pch.quizShowAnswer

B — No — a 0-edge can improve a node's distance after it has been popped, so marking it visited produces answers that are too large — This is the single most common way to break the algorithm, and it fails quietly: you get a valid path length, just not the shortest. Termination comes from the strict `dist[v] + wt < dist[u]` guard, not from a visited set.
What happens if the guard is written `<=` instead of `<`?

pch.quizShowAnswer

B — It loops forever on any graph containing a 0-weight edge, because equal-distance pushes never stop — A 0-edge between two nodes at the same distance re-pushes each other endlessly. Strictness is what makes progress monotone.
In LC 1368, where does the weight live?

pch.quizShowAnswer

B — On the move: following the direction the cell's arrow points is free, any other of the four moves costs 1 redirection — Modelling the weight as a property of the move is the insight that turns the problem into eleven lines. The grid's numbers are edge weights, not node values.
The weights turn out to be 0, 1 and 2. What now?

pch.quizShowAnswer

B — The two-layer invariant fails, so use Dijkstra — or a bucket queue with k+1 buckets if the weights are small integers — 0 and k for a single fixed k is still fine, because only the ordering matters. Three or more distinct weights is not: a node at d+2 has no correct end of the deque to go to.
Dijkstra already passes the problem. Why mention 0-1 BFS in an interview?

pch.quizShowAnswer

B — Because it fits the weights exactly — O(V + E) with no ordering structure — which shows you noticed the weights are binary, not because Dijkstra times out — log(10^5) is about 17, so Dijkstra rarely times out on grid problems. Claiming a TLE you have not measured is worse than naming the real reason: the structure of the weights.

Recall card

Cue — shortest path where every move costs 0 or 1; usually a grid asking for the minimum number of things to change.
Structure — deque. 0-edge → appendleft (same layer), 1-edge → append (next layer).
Guard — push only when dist[v] + wt < dist[u], strictly. That replaces Dijkstra’s stale-entry check and makes duplicate entries harmless.
No visited set — a 0-edge can improve an already-popped node.
Cost — $O(V + E)$ time, $O(V)$ space; Dijkstra’s answer without the $\log V$ .
Modelling — the weight belongs to the move, not the cell. Free = the move the input already permits; 1 = anything you had to change.
Boundary — 0 and one fixed $k$ : fine. Three distinct weights: Dijkstra, or a bucket queue for small integer weights.

Recap

0-1 BFS is the shortest-path algorithm for binary weights: a deque replaces the heap because at most two distances are ever in flight.
The template is BFS plus one branch — appendleft for weight 0, append for weight 1 — and minus the visited set, which would be a bug here.
The hard part is never the algorithm; it is seeing the 0-1 graph inside a grid statement that never mentions weights. Free moves are the ones the input already allows, paid moves are the ones you had to change.
It composes with extra state: “break at most k walls” is the same deque over (cell, budget) states.
Three or more distinct weights breaks the invariant. Know where the line is, and say so before someone asks.

Next: Union-Find Problem Patterns — the other way to answer connectivity questions, when the query is “are these two connected” rather than “how far”.

pch.coffeeTagline

pch.coffeeCta

pch.feedbackHeading

pch.feedbackSubheading