0-1 BFS: The Shortest-Path Trick Interviewers Love to See#
When every edge in a graph has weight 0 or 1, you do not need Dijkstra's priority queue. A double-ended queue (deque) gives you the same correct distances in O(V + E) instead of O((V + E) log V). This comes up more often in coding interviews than people expect, usually disguised as a grid problem.
How to recognise a 0-1 BFS problem#
Look for phrasing like:
- "Minimum number of walls to remove to reach the exit"
- "Minimum cost to make at least one valid path in a grid" (following the arrow is free, changing it costs 1)
- "Minimum number of flips / reversals of directed edges"
- "Move freely inside a region, pay 1 to cross into another one"
The pattern: some moves are free, others cost exactly one unit.
The idea in one sentence#
Pop the front of the deque; for a 0-weight edge push the neighbour to the front, for a 1-weight edge push it to the back. The deque then always holds nodes in non-decreasing distance order (at most two distinct distance values at once), which is exactly the invariant Dijkstra's heap was maintaining for you.
Python template#
from collections import deque
def zero_one_bfs(n, adj, src):
INF = float("inf")
dist = [INF] * n
dist[src] = 0
dq = deque([src])
while dq:
u = dq.popleft()
for v, w in adj[u]: # w is 0 or 1
nd = dist[u] + w
if nd < dist[v]:
dist[v] = nd
if w == 0:
dq.appendleft(v)
else:
dq.append(v)
return dist
Note there is no visited set. A node can be pushed more than once, but only when its distance actually improves, and that can happen at most twice per node in practice, so the total work stays linear.
Worked example: minimum obstacles to remove#
Grid of 0s (empty) and 1s (obstacle). Moving into an empty cell costs 0, moving into an obstacle costs 1 (you remove it). Answer = distance to the bottom-right cell.
def minimum_obstacles(grid):
m, n = len(grid), len(grid[0])
dist = [[float("inf")] * n for _ in range(m)]
dist[0][0] = 0
dq = deque([(0, 0)])
while dq:
r, c = dq.popleft()
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n:
w = grid[nr][nc]
if dist[r][c] + w < dist[nr][nc]:
dist[nr][nc] = dist[r][c] + w
(dq.appendleft if w == 0 else dq.append)((nr, nc))
return dist[m-1][n-1]
Common mistakes interviewers watch for#
- Marking nodes visited on push. That is plain-BFS muscle memory and it breaks correctness here, because a cheaper 0-edge path may arrive later.
- Using it with weights other than 0/1. For small integer weights up to K, use Dial's algorithm (bucket queue) instead.
- Forgetting the complexity argument. Say it out loud: each node's distance only decreases, the deque is ordered, so it is O(V + E).
How to talk about it in the interview#
Start with "this is a shortest path with weights 0 and 1, so Dijkstra works, but a deque-based 0-1 BFS is linear." Then write the template, then adapt it. Interviewers reward that framing more than the code itself: it shows you picked the tool deliberately.
If you practise these patterns out loud, a real-time helper such as Linkjob AI can listen to mock interview questions and suggest structure for your explanation while you rehearse. (Disclosure: I work on Linkjob AI.)
Practice list#
- Minimum Obstacle Removal to Reach Corner
- Minimum Cost to Make at Least One Valid Path in a Grid
- Minimum Moves to Move a Box to Their Target Location (state-space variant)
- Reverse edges to reach node N (classic 0-1 BFS on directed graphs)