0-1 BFS with a Deque
Shortest paths when weights are 0 or 1.
0-1 BFS with a Deque is a free Coding Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
A Special Kind of Graph
Some graphs only have edge weights of 0 or 1. There you can beat Dijkstra with a simpler, faster trick.
Meet 0-1 BFS
0-1 BFS finds shortest paths on 0/1-weighted graphs in linear time, with no heap and no log factor at all.
The Tool: a Deque
Swap the heap for a deque, a queue you can push to and pop from both the front and the back.
from collections import deque
dq = deque([src])The Core Insight
A 0-weight edge keeps the same distance, while a 1-weight edge adds one. The deque keeps both groups in order.
Front for Zero Edges
Cross a 0-edge? appendleft the neighbor so it is processed next, since it costs no extra distance.
dq.appendleft(v)Back for One Edges
Cross a 1-edge? append the neighbor to the back, because it sits one layer farther from the source.
dq.append(v)Pop From the Front
Always popleft the current node. This keeps the deque sorted by distance, just like a layered BFS would.
u = dq.popleft()Relax With the Weight
Relax each edge: a new distance of dist[u] plus the edge weight, then push to front or back by that weight.
nd = dist[u] + w
if nd < dist[v]:
dist[v] = ndWhy It Stays Sorted
The deque holds at most two distinct distances at once. That invariant is exactly why front and back placement works.
The Linear Speed
Because there is no heap, 0-1 BFS runs in O(V + E), noticeably faster than Dijkstra on the same graph.
When to Reach for It
Use it whenever moves are free or cost one, like grids where some steps are blocked and others are open.
Quick Check
You relax a neighbor across an edge of weight 0. Where does it go?
Recap: 0-1 BFS
With a deque, push 0-edges to the front and 1-edges to the back. You get shortest paths in clean O(V+E) time. ⚡
Frequently asked questions
Is the “0-1 BFS with a Deque” lesson free?
Yes — the full text of “0-1 BFS with a Deque” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “0-1 BFS with a Deque”?
Shortest paths when weights are 0 or 1. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “0-1 BFS with a Deque” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Dijkstra with a Heap
- 0-1 BFS with a Deque
- Bellman-Ford & Negative Edges
- Floyd-Warshall All-Pairs